← Math

Count Primes

Medium
Python
def count_primes(n):
    if n<2: return 0
    sieve=[True]*n; sieve[0]=sieve[1]=False
    for i in range(2,int(n**0.5)+1):
        if sieve[i]:
            for j in range(i*i,n,i): sieve[j]=False
    return sum(sieve)
Java
public int countPrimes(int n){
    if(n<2) return 0;
    boolean[] s=new boolean[n]; Arrays.fill(s,true); s[0]=s[1]=false;
    for(int i=2;(long)i*i<n;i++) if(s[i]) for(int j=i*i;j<n;j+=i) s[j]=false;
    int c=0; for(boolean b:s) if(b) c++;
    return c;
}

Key Insight

Sieve of Eratosthenes. sum(sieve) vs explicit loop. Java needs long cast.

Python → Java Differences

  • [True]*n vs Arrays.fill()
  • sum(sieve) vs explicit loop
  • Java (long)i*i prevents overflow
Python
def count_primes(n):
    if n<2: return 0
    sieve=[True]*n; sieve[0]=sieve[1]=False
    for i in range(2,int(n**0.5)+1):
        if sieve[i]:
            for j in range(i*i,n,i): sieve[j]=False
    return sum(sieve)
Java
public int countPrimes(int n){
    if(n<2) return 0;
    boolean[] s=new boolean[n]; Arrays.fill(s,true); s[0]=s[1]=false;
    for(int i=2;(long)i*i<n;i++) if(s[i]) for(int j=i*i;j<n;j+=i) s[j]=false;
    int c=0; for(boolean b:s) if(b) c++;
    return c;
}

Algorithm Steps

1. Create sieve
2. Mark composites
3. Count primes
← Previous All Math Next →