Inspired by Arulx Z :- Counting Primes

I used Sieve of Eratosthenes (with some optimizations) because it's easy to implement. Weird thing with this code is that it's actually pretty fast.

 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
39
40
41
42
43
44
45
46

/* At the end,
 * 0 = composite
 * non-zero = prime
 */

final int lim = 31032001; // exclusive

int n[] = new int[lim - 2]; //exclude 1
for(int i = 2; i <= lim - 1; i++) //initialize the array with integers from 2 to lim
{
  if((i & 1) == 0) //evens are not primes f & 1 return 0 if f % 2 == 0
  {
    n[i - 2] = 0;
  }
  else
  {
    n[i - 2] = i;
  }
}

n[0] = 2;

int p = 3; //start with a prime. Since 2 is already eliminated, start with 3

while(p * p < lim)
{
  for(int i = p * p; i < lim; i += p + p) //remvove multiples of prime. Start at p * p
  {
    n[i - 2] = 0;
  }

  while(n[(p += 2) - 2] == 0) //find next non zero number. This is guaranteed to be a prime.
    ;
}

int count = 0;

for(int i = 0; i < lim - 2; i++) //print non zero numbers
{
  if(n[i] != 0)
  {
    count += 1;
  }
}

System.out.println(count);

Takes about 0.47 secs.

In Matlab,

length(primes(31032001))

primes(N) returns a row matrix of primes less than or equal to 31032001. length(X) returns the length of matrix X.

Sieve of Eratosthenes in Python (not well-optimized code...)

Time : about 5.4 seconds in my computer (0.8 seconds in pypy!)

import math

def count_primes(n):
    P = [0, 0]+[1]*(n-1) # 0 ... n

    for m in xrange(2, int(math.sqrt(n))+1):
        if P[m] != 0: # 0 = checked
            for i in xrange(m+m, n+1, m):
                P[i] = 0

    return sum(P)

if __name__ == '__main__':
    print count_primes(31032001)