Counting Primes

The sieve of Erastrosthenes is the most efficient!

Note that we only need to check divisors up to $\sqrt{1\:234\:567\:891\:011} \approx 1\:111\:111$ .

I generated the sieve of Erastosthenes in "pages" of $1\:111\:112$ numbers. For the first page, we start at $p = 2$ and cross out all its multiples on the page. Then we use the first (not crossed-out) number, $p = 3$ , and cross out its multiples. And so on. Meanwhile, we keep a table of all primes we encountered. These are all the prime numbers we need for the entire search.

We also keep a table "next", which tells where the first multiple of a prime number $p$ will be on the next page.

For each of the (slightly more than 1.1 million) pages, we cross out all multiples of all primes previously generated. The starting point comes from the table "next", and we update the value of "next" once the page is done. All not crossed-out numbers on the page must be prime; there is no need to store them.

The last page takes special care, because we must not count all prime numbers on it.

Running this Java program took slightly more than one hour.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

final long top = 1234567891011L;
final int pSz = 1111112;             // page size; must be > largest prime to be checked
final int pCount = (int)(top/pSz);   // number of pages
final int pRest = (int)(top%pSz);    // position of "top" on the last page

int  prime[] = new int[pSz];         // table of primes to check
int  next[] = new int[pSz];          // where is the first multiple of a prime on the next page
boolean sieve[] = new boolean[pSz];  // sieve of Erastosthenes for this page; false = crossed out

int nP = 0;                          // number of primes in "prime"
long p = 0;                          // number of primes encountered

for (int i = 0; i < pSz; i++) sieve[i] = true;      // reset sieve

for (int n = 2; n < pSz; n++) if (sieve[n]) {       // not crossed out? 
    prime[nP] = (int)n;                             // record as a prime number

    int k = n + n;
    while (k < pSz) { sieve[k] = false; k += n; }   // cross out multiples of n
    k -= pSz; next[nP] = k;                         // remember location of next multiple for next page

    nP++; p++;                                      // increase prime number count
}

for (int pg = 1; pg <= pCount; pg++) {              // generate sieve page by page
  for (int i = 0; i < pSz; i++) sieve[i] = true;    // reset the sieve

  for (int j = 0; j < nP; j++) {                    // use all recorded prime numbers
      int n = prime[j], k = next[j];         
      while (k < pSz) { sieve[k] = false; k += n; } // cross out its multiples
      k -= pSz; next[j] = k;                        // remember location of next multiple for next page
  }
  int max = (pg == pCount) ? pRest : pSz;           // on the last page, don't count all the primes

  for (int i = 0; i < max; i++) if (sieve[i]) p++;  // not crossed out? then it is a prime
}

out.println(p);

Output: $\boxed{46063874346}$ .

In this world, we ought to learn to be able to identify and to know how to apply to be able to solve most tedious problem. You may think that an hour is fast, some people can complete it within few seconds. I can't believe this before I realize.

Answer: $\boxed{46,063,874,346}$