Primes

Algorithm Analysis

Using the Sieve of Eratosthenes, we'll fill an array: primes[i] = 1 if $i$ is prime and primes[i] = 0 otherwise. The size of the primes array is $1 0^{7}$ .

Based on the primes array, we'll fill the cnt array, where cnt[i] contains the number of prime numbers from 1 to $i$ :

if $i$ is prime, then we set cnt[i] = cnt[i – 1] + 1;
if $i$ is composite, then we set cnt[i] = cnt[i – 1].

Numbers 0 and 1 are not prime, we set cnt[0] = cnt[1] = 0.

Then the number of prime numbers in the interval [ $m$ ; $n$ ] equals cnt[m] – cnt[n – 1].

Example

The filled primes and cnt arrays look like this:

The number of prime numbers in the interval [4; 12] equals cnt[12] – cnt[3] = 5 – 2 = 3. The prime numbers in the interval are 5, 7, and 11.

Algorithm Implementation

Declare working arrays.

#define MAX 10000100
char primes[MAX];
int cnt[MAX];

The gen_primes function starts the Sieve of Eratosthenes and fills the primes array.

void gen_primes(void)
{
    int i, j;
    for(i = 0; i < MAX; i++) primes[i] = 1;
    for(i = 2; i < sqrt(MAX); i++)
        if (primes[i])
            for(j = i * i; j < MAX; j += i)
                primes[j] = 0;
}

The main part of the program. Start the Sieve of Eratosthenes.

gen_primes();
memset(cnt,0,sizeof(cnt));

Fill the cnt array, the $i$ th element of which contains the number of prime numbers from 1 to $i$ .

for (i = 2; i < MAX; i++)
    if (primes[i]) cnt[i] = cnt[i-1] + 1; else cnt[i] = cnt[i-1];

Sequentially process requests.

while(scanf("%d %d",&a,&b) == 2)
    printf("%d\n",cnt[b] - cnt[a-1]);

Algorithm Implementation – bitset

#include <cstdio>
#include <bitset>
#include <cmath>
#define MAX 10000001
using namespace std;

int a, b, i;
bitset<MAX> primes;
int cnt[MAX];

void gen_primes(void)
{
    primes.flip(); // set all to 1
    primes.reset(0); primes.reset(1);
    for (int i = 2; i <= sqrt(MAX); i++)
        if (primes.test(i))
            for (int j = i * i; j < MAX; j += i)
                primes.reset(j);
}

int main(void)
{
    gen_primes();
    memset(cnt, 0, sizeof(cnt));
    for (i = 2; i < MAX; i++)
        if (primes.test(i)) cnt[i] = cnt[i - 1] + 1; 
        else cnt[i] = cnt[i - 1];
    while (scanf("%d %d", &a, &b) == 2)
        printf("%d\n\n", cnt[b] - cnt[a - 1]);
    return 0;
}

Java Implementation

import java.util.*;

public class Main
{
    final static int MAX_SIZE = 10000001;
    static BitSet primes = new BitSet(MAX_SIZE);
    static int cnt[] = new int[MAX_SIZE];

    public static void Eratosthenes()
    {
        primes.set(2, MAX_SIZE, true);
        for (int i = 2; i < Math.sqrt(MAX_SIZE); i++)
        {
            if (primes.get(i))
                for (int j = i * i; j < MAX_SIZE; j += i)
                    primes.set(j, false);
        }
    }

    public static void main(String args[]) 
    {
        Scanner con = new Scanner(System.in);
        Eratosthenes();
        for (int i = 2; i < MAX_SIZE; i++)
            if (primes.get(i)) cnt[i] = cnt[i-1] + 1; 
            else cnt[i] = cnt[i-1];
        while(con.hasNextInt())
        {
            int a = con.nextInt();
            int b = con.nextInt();
            System.out.println(cnt[b] - cnt[a -1]);
            System.out.println();
        }
        con.close();
    }
}

Python Implementation – 10 seconds

import sys

def seive_of_eratosthenes(n):
    is_prime = [True for _ in range(n + 1)]
    is_prime[0], is_prime[1] = False, False

    for i in range(2, int(n ** 0.5) + 1):
        for j in range(i * i, n + 1, i):
            is_prime[j] = False

    return is_prime

prime = seive_of_eratosthenes(10000001)
cnt = [0 for _ in range(10000001)]
for i in range(2,10000001):
    if prime[i]: cnt[i] = cnt[i-1] + 1;
    else: cnt[i] = cnt[i-1];

for s in sys.stdin:
    if (s == "\n") : continue;
    a, b = map(int,s.split())
    print(cnt[b] - cnt[a - 1])
    print()