3843. Primes

 

Let m and n (2 ≤ m < n ≤ 107) be two integers. Consider the following set:

Prime(m, n) = { p | p prime, m ≤ p ≤ n }

Find the cardinality of the set Prime(m, n).

 

Input. Consists of several tests. The input of each test is represented on a single line. Any two consecutive tests are separated by an empty line. For each test, the values for m and n are given on the same line, separated by exactly one space.

 

Output. For each test, the result will be written on a different line (the tests will have the same order as in the input). The results of any two consecutive tests will be separated by an empty line. For each test, the result will be the cardinal of the set Prime(m, n).

 

Sample input

Sample output

4 12

 

70 110

 

5 150

3

 

10

 

33

 

 

SOLUTION

sieve of Eratosthenes

 

Algorithm analysis

Using the sieve of Eratosthenes, fill the array: primes[i] = 1 if i is prime and primes[i] = 0 otherwise. The size of the primes array is 107.

Based on the primes array, fill in the cnt array, where cnt[i] contains the number of primes from 1 to i:

·        if i is prime, assign cnt[i] = cnt[i – 1] + 1;

·        if i is composite, assign cnt[i] = cnt[i – 1];

Then the number of primes in the interval [m; n] equals to cnt[m] – cnt[n – 1].

 

Example

The filled arrays primes and cnt have the form:

 

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

 

Algorithm realization

Declare the working arrays.

 

#define MAX 10000100

char primes[MAX];

int cnt[MAX];

 

Function gen_primes runs 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. Run the sieve of Eratosthenes.

 

gen_primes();

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

 

Fill the cnt array, its i-th element contains the number of primes 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 the queries.

 

while(scanf("%d %d",&a,&b) == 2)

 

The number of primes in the interval [a; b] equals to cnt[b] – cnt[a – 1].

 

  printf("%d\n",cnt[b] - cnt[a-1]);

 

Algorithm realization – 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 realization

 

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 realization – 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()