Sadə (#3843) - Basecamp

Alqoritm Analizi

Eratostenin süzgəci istifadə edərək, bir massivi dolduracağıq: primes[i] = 1 əgər $i$ əsasdirsə və primes[i] = 0 əks halda. primes massivinin ölçüsü $1 0^{7}$ -dir.

primes massivinə əsaslanaraq, cnt massivini dolduracağıq, burada cnt[i] 1-dən $i$ -ə qədər olan əsas ədədlərin sayını ehtiva edir:

əgər $i$ əsasdirsə, onda cnt[i] = cnt[i – 1] + 1 təyin edirik;
əgər $i$ mürəkkəbdirsə, onda cnt[i] = cnt[i – 1] təyin edirik.

0 və 1 əsas ədəd deyil, biz cnt[0] = cnt[1] = 0 təyin edirik.

Sonra [ $m$ ; $n$ ] aralığında olan əsas ədədlərin sayı cnt[m] – cnt[n – 1]-ə bərabərdir.

Nümunə

Doldurulmuş primes və cnt massivləri belə görünür:

Aralıqdakı [4; 12] əsas ədədlərin sayı cnt[12] – cnt[3] = 5 – 2 = 3-ə bərabərdir. Aralıqdakı əsas ədədlər 5, 7 və 11-dir.

Alqoritm İmplementasiyası

İşləyən massivləri elan edin.

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

gen_primes funksiyası Eratostenin süzgəcini başladır və primes massivini doldurur.

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

Proqramın əsas hissəsi. Eratostenin süzgəcini başladın.

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

1-dən $i$ -ə qədər olan əsas ədədlərin sayını ehtiva edən cnt massivini doldurun.

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

Ardıcıl olaraq sorğuları işləyin.

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

Alqoritm İmplementasiyası – 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 İmplementasiyası

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 İmplementasiyası – 10 saniyə

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