Простые (#3843)

Анализ алгоритма

Используя решето Эратосфена, заполним массив: primes[i] = 1, если $i$ простое и primes[i] = 0 иначе. Размер массива primes составляет $1 0^{7}$ .

На основе массива primes заполним массив cnt, в котором cnt[i] содержит количество простых чисел от 1 до $i$ :

если $i$ простое, то положим cnt[i] = cnt[i – 1] + 1;
если $i$ составное, то положим cnt[i] = cnt[i – 1].

Числа 0 и 1 не являются простыми, положим cnt[0] = cnt[1] = 0.

Тогда количество простых чисел на отрезке [ $m$ ; $n$ ] равно cnt[m] – cnt[n – 1].

Пример

Заполненные массивы primes и cnt имеют вид:

Количество простых чисел на промеутке [4; 12] равно cnt[12] – cnt[3] = 5 – 2 = 3. Простыми числами на промежутке будут 5, 7 и 11.

Реализация алгоритма

Объявим рабочие массивы.

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

Функция gen_primes запускает решето Эратосфена и заполняет массив primes.

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;
}

Основная часть программы. Запускаем решето Эратосфена.

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

Заполняем массив cnt, $i$ -ый элемент которого содержит количество простых чисел от 1 до $i$ .

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

Последовательно обрабатываем запросы.

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

Реализация алгоритма – 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 реализация

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 реализация – 10 секунд

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