Eratosfen xəlbiri#4739

Eratosfen xəlbiri (Həll təhlili)

Eratosthen süzgəc algoritmindən istifadə edərək, $p r im es$ massivini dolduraq, burada

$p r im es [i] = 1$ primes[i] = 1, əgər $i$ sadədirsə;
$p r im es [i] = 0$ primes[i] = 0, əgər $i$ mürəkkəbdirsə;

$a$ -dan $b$ -yədək olan intervalda $p r im es [i] = 1$ primes[i] = 1 olan bütün ədədləri çıxarış edək.

Nümunə

Doldurulmuş $p r im es$ massivi belə görünür:

$[1; 10]$ intervalında sadə ədədlər $2, 3, 5, 7$ 2, 3, 5, 7 olacaq.

Algoritmin tətbiqi

İşçi $p r im es$ massivini elan edək.

#define MAX 100001
int primes[MAX];

gen_primes funksiyası Eratosthen süzgəcini həyata keçirir. $p r im es$ massivini dolduraq. $0$ və $1$ ədədləri sadə deyil.

void gen_primes(void)
{
  int i, j;
  for (i = 0; i < MAX; i++) primes[i] = 1;
  primes[0] = primes[1] = 0;
  for (i = 2; i * i <= MAX; i++)
    if (primes[i])
      for (j = i * i; j < MAX; j += i) primes[j] = 0;
}

C++

Proqramın əsas hissəsi. $p r im es$ massivini dolduraq.

gen_primes();

Giriş məlumatlarını oxuyuruq.

scanf("%d %d", &a, &b);

$a$ -dan $b$ -yədək olan bütün sadə ədədləri çıxarış edirik.

for (i = a; i <= b; i++)
  if (primes[i]) printf("%d ", i);
printf("\n");

Algoritmin tətbiqi — bitset

Sadə ədədlər haqqında məlumat saxlamaq üçün $p r im es$ dəyişənini bitset tipində elan edək.

#define MAX 100001
bitset<MAX> primes;

gen_primes funksiyası Eratosthen süzgəcini həyata keçirir. $p r im es$ massivini dolduraq. $0$ və $1$ ədədləri sadə deyil.

void gen_primes(void)
{
  primes.flip(); // hamısını 1 olaraq təyin et
  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);
}

C++

Proqramın əsas hissəsi. $p r im es$ massivini dolduraq.

gen_primes();

Giriş məlumatlarını oxuyuruq.

scanf("%d %d", &a, &b);

$a$ -dan $b$ -yədək olan bütün sadə ədədləri çıxarış edirik.

for (i = a; i <= b; i++)
  if (primes.test(i)) printf("%d ", i);
printf("\n");

Java tətbiqi

import java.util.*;

public class Main 
{
  final static int MAX_SIZE = 100001;
  static BitSet bits = new BitSet(MAX_SIZE);
   
  public static void Eratosthenes()
  {
    bits.set(2, MAX_SIZE, true);
    for (int i = 2; i < Math.sqrt(MAX_SIZE); i++)
    {
      if (bits.get(i))
        for (int j = i * i; j < MAX_SIZE; j += i)
          bits.set(j, false);
    }
  }
	 
  public static void main(String args[]) 
  {
    Scanner con = new Scanner(System.in);
    Eratosthenes();
    int a = con.nextInt();
    int b = con.nextInt();
    for (int i = a; i <= b; i++)
      if (bits.get(i)) System.out.print(i + " ");
    System.out.println();
    con.close();
  }
}

Java

Python tətbiqi

seive_of_eratosthenes funksiyası Eratosthen süzgəcini həyata keçirir. $i s_{p} r im e$ is_prime siyahısını dolduraq və qaytaraq. $0$ və $1$ ədədləri sadə deyil.

def seive_of_eratosthenes(n):
  is_prime = [True] * (n+1)
  is_prime[0], is_prime[1] = False, False

  for i in range(2, int(n ** 0.5) + 1):
    if is_prime[i]:
      for j in range(i * i, n + 1, i):
        is_prime[j] = False

  return is_prime

Python

Proqramın əsas hissəsi. $p r im e$ massivini dolduraq.

prime = seive_of_eratosthenes(100000)

Giriş məlumatlarını oxuyuruq.

a, b = map(int, input().split())

$a$ -dan $b$ -yədək olan bütün sadə ədədləri çıxarış edirik.

for i in range (a, b + 1):
  if prime[i]: print(i,end=' ')