3843. Простые

Пусть m и n (2 ≤ m < n ≤ 10⁷) – целые числа. Рассмотрим следующее множество:

Prime(m, n) = { p | p простое, m ≤ p ≤ n }

Вычислить мощность множества Prime(m, n).

Вход. Состоит из нескольких тестов. Два последовательных теста разделены пустой строкой. Для каждого теста в отдельной строке заданы числа m и n.

Выход. Для каждого теста вывести результат в отдельной строке. Результаты соседних тестов разделять пустой строкой. Для каждого теста вывести мощность множества Prime(m, n).

Пример входа	Пример выхода
4 12 70 110 5 150	3 10 33

РЕШЕНИЕ

решето Эратосфена

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

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

На основе массива 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)

Количество простых чисел на промежутке [a; b] равно cnt[b] – cnt[a – 1].

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