THINK FIRST·CODE LATER

← All labs

Counting primes three ways

Problem

How many primes are there up to n? Write PrimeCounting, which answers with three algorithms and counts the basic operations of each:

  1. for every number, trial division by every d with d² ≤ number;
  2. trial division by the primes found so far only (kept in a list), again while p² ≤ number;
  3. the sieve of Eratosthenes: for each number not yet crossed out, cross out its multiples starting at its square.

Print the number of primes, the three operation counts, whether the three results agree, and the last five primes. For the input

1000

the program prints

Primes up to 1000: 168
Trial division by all numbers: 5288 divisions
Trial division by primes only: 2801 divisions
Sieve of Eratosthenes: 1411 crossings-out
All three agree: true
Last primes: 971 977 983 991 997

Run it for n = 1000, 10 000 and 100 000. When n is multiplied by 10, by how much does each count grow?

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d6-9-data-1.txt

1000
What your program must print for d6-9-data-1.txt
Primes up to 1000: 168
Trial division by all numbers: 5288 divisions
Trial division by primes only: 2801 divisions
Sieve of Eratosthenes: 1411 crossings-out
All three agree: true
Last primes: 971 977 983 991 997

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d6-9-data-1.txt

Windows PowerShell does not understand <:

Get-Content d6-9-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.