Простые (#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()