Sito Atkina jest bardziej zaawansowaną wersją Sita Eratostenesa, przeznaczoną do szybszego generowania liczb pierwszych. Algorytm ten jest bardziej skomplikowany, ale oferuje lepszą wydajność przy dużych zakresach liczb.
Podstawy algorytmu Sito Atkina
Algorytm Sito Alkina działa na zasadzie eliminacji liczb z kandydatów na liczby pierwsze za pomocą wzorów kwadratowych i modulo. W przeciwieństwie do algorytmu Sito Eratostenesa, który działa na zasadzie eliminacji wielokrotności liczb pierwszych. Sito Alkina wykorzystuje bardziej złożone kryteria, aby bezpośrednio oznaczyć liczby pierwsze.
Kroki algorytmu Sito Atkina
Inicjalizacja
- Tworzymy listę liczby o długości n + 1, w której każda pozycja początkowo przyjmuje wartość False. Pozycja i w tej liście będzie oznaczała, czy liczba i jest liczbą pierwszą.
- Ustawiamy liczby[2] i liczby[3] na True, ponieważ 2 i 3 są liczbami pierwszymi.
Generowanie kandydatów na liczby pierwsze
Dla każdej pary liczb całkowitych (x, y) takich, że 1≤x2+y2≤n:
- Jeżeli x2+y2 jest nieparzyste i 4x2+y2≤n, to zmieniamy stan liczby[4x2 + y2] na przeciwny (flip).
- Jeżeli 3x2+y2≤n i 3x2+y2 mod 12 = 7, to zmieniamy stan liczby[3x2 + y2] na przeciwny.
- Jeżeli 3x2−y2≤n, x>y i 3x2−y2 mod 12 = 11, to zmieniamy stan liczby[3x2 - y2] na przeciwny.
Eliminacja kwadratów liczb pierwszych
Dla każdej liczby i od 5 do pierwiastek (n):
- Jeżeli liczby[i] jest True, to oznacza, że i jest liczbą pierwszą, a więc eliminujemy wszystkie wielokrotności i2 (ustawiamy na False), ponieważ te liczby nie mogą być pierwsze.
Zbieranie wyników
Zbieramy wszystkie liczby, które pozostały oznaczone jako True.
Poniższe przykłady kodów programów generują liczby pierwsze do 10000 (n - ustawione jest jako 10000)
Sito Atkina w języku Python
import math
def sito_alkina(n):
# Inicjalizacja
liczby = [False] * (n + 1)
if n > 2:
liczby[2] = True
if n > 3:
liczby[3] = True
# Generowanie kandydatów na liczby pierwsze
sqrt_n = int(math.sqrt(n)) + 1
for x in range(1, sqrt_n):
for y in range(1, sqrt_n):
num1 = 4 * x**2 + y**2
if num1 <= n and (num1 % 12 == 1 or num1 % 12 == 5):
liczby[num1] = not liczby[num1]
num2 = 3 * x**2 + y**2
if num2 <= n and num2 % 12 == 7:
liczby[num2] = not liczby[num2]
num3 = 3 * x**2 - y**2
if x > y and num3 <= n and num3 % 12 == 11:
liczby[num3] = not liczby[num3]
# Eliminacja kwadratów liczb pierwszych
for i in range(5, sqrt_n):
if liczby[i]:
for j in range(i**2, n + 1, i**2):
liczby[j] = False
# Zbieranie wyników
primes = [2, 3] + [i for i in range(5, n + 1) if liczby[i]]
return primes
# Ustawiamy wartość n na 10000
n = 10000
# Znajdujemy wszystkie liczby pierwsze mniejsze niż 10000
primes = sito_alkina(n)
# Wyświetlamy wynik
print(primes)
Złożoność obliczeniowa
Algorytm Sito Alkina ma złożoność czasową O(n/log log n), co jest bardziej efektywne niż O(n log log n) dla Sita Eratostenesa. Złożoność pamięciowa wynosi O(n).
Sito Alkina jest bardziej zaawansowanym algorytmem do generowania liczb pierwszych, który jest wydajniejszy niż klasyczne Sito Eratostenesa dla dużych zakresów. Dzięki zastosowaniu bardziej skomplikowanych kryteriów selekcji liczb pierwszych, pozwala na szybsze generowanie dużych zbiorów liczb pierwszych.
Sito Atkina w języku C++
#include <iostream>
#include <vector>
#include <cmath>
std::vector<int> sitoAtkina(int limit) {
std::vector<bool> liczby(limit + 1, false);
for (int x = 1; x * x <= limit; x++) {
for (int y = 1; y * y <= limit; y++) {
int n = 4 * x * x + y * y;
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
liczby[n] = !liczby[n];
}
n = 3 * x * x + y * y;
if (n <= limit && n % 12 == 7) {
liczby[n] = !liczby[n];
}
n = 3 * x * x - y * y;
if (x > y && n <= limit && n % 12 == 11) {
liczby[n] = !liczby[n];
}
}
}
for (int i = 5; i * i <= limit; i++) {
if (liczby[i]) {
for (int j = i * i; j <= limit; j += i * i) {
liczby[j] = false;
}
}
}
std::vector<int> primes;
if (limit > 2) primes.push_back(2);
if (limit > 3) primes.push_back(3);
for (int i = 5; i <= limit; i++) {
if (liczby[i]) primes.push_back(i);
}
return primes;
}
int main() {
int limit = 10000;
std::vector<int> primes = sitoAtkina(limit);
for (int prime : primes) {
std::cout << prime << " ";
}
return 0;
}
Sito Atkina w języku Java
import java.util.ArrayList;
import java.util.List;
public class SitoAtkina {
public static List<Integer> sitoAtkina(int limit) {
boolean[] liczby = new boolean[limit + 1];
for (int x = 1; x * x <= limit; x++) {
for (int y = 1; y * y <= limit; y++) {
int n = 4 * x * x + y * y;
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
liczby[n] = !liczby[n];
}
n = 3 * x * x + y * y;
if (n <= limit && n % 12 == 7) {
liczby[n] = !liczby[n];
}
n = 3 * x * x - y * y;
if (x > y && n <= limit && n % 12 == 11) {
liczby[n] = !liczby[n];
}
}
}
for (int i = 5; i * i <= limit; i++) {
if (liczby[i]) {
for (int j = i * i; j <= limit; j += i * i) {
liczby[j] = false;
}
}
}
List<Integer> primes = new ArrayList<>();
if (limit > 2) primes.add(2);
if (limit > 3) primes.add(3);
for (int i = 5; i <= limit; i++) {
if (liczby[i]) primes.add(i);
}
return primes;
}
public static void main(String[] args) {
int limit = 10000;
List<Integer> primes = sitoAtkina(limit);
System.out.println(primes);
}
}
Sito Atkina w języku JavaScript
function sitoAtkina(limit) {
let liczby = Array(limit + 1).fill(false);
for (let x = 1; x * x <= limit; x++) {
for (let y = 1; y * y <= limit; y++) {
let n = 4 * x * x + y * y;
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
liczby[n] = !liczby[n];
}
n = 3 * x * x + y * y;
if (n <= limit && n % 12 == 7) {
liczby[n] = !liczby[n];
}
n = 3 * x * x - y * y;
if (x > y && n <= limit && n % 12 == 11) {
liczby[n] = !liczby[n];
}
}
}
for (let i = 5; i * i <= limit; i++) {
if (liczby[i]) {
for (let j = i * i; j <= limit; j += i * i) {
liczby[j] = false;
}
}
}
let primes = [];
if (limit > 2) primes.push(2);
if (limit > 3) primes.push(3);
for (let i = 5; i <= limit; i++) {
if (liczby[i]) primes.push(i);
}
return primes;
}
let limit = 10000;
let primes = sitoAtkina(limit);
console.log(primes);
Komentarze