How many primes are there up to n? Write PrimeCounting, which answers with three algorithms and counts the basic operations of each:
- for every number, trial division by every d with d² ≤ number;
- trial division by the primes found so far only (kept in a list), again while p² ≤ number;
- 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?