Liczby pierwsze do 100 można wyznaczyć na kilka sposobów. Poniżej zostaną omówione trzy popularne metody: Sito Eratostenesa, Sito Atkina i prosty algorytm sprawdzania podzielności.
1. Sito Eratostenesa
Sito Eratostenesa to jeden z najstarszych i najprostszych algorytmów do wyznaczania liczb pierwszych.
Algorytm ten działa w następujący sposób:
- Tworzymy listę liczb od 2 do n (w tym przypadku do 100).
- Zaczynamy od pierwszej liczby (2) i oznaczamy ją jako pierwszą.
- Usuwamy wszystkie wielokrotności tej liczby.
- Przechodzimy do następnej liczby w liście, która nie została usunięta, i powtarzamy krok 3.
- Powtarzamy kroki 3-4, aż przejdziemy przez całą listę.
Implementacja Sita Eratostenesa do wyznaczenia liczb pierwszych do 100 w języku Python
def sieve_of_eratosthenes(limit):
primes = [True] * (limit + 1)
p = 2
while (p * p <= limit):
if primes[p]:
for i in range(p * p, limit + 1, p):
primes[i] = False
p += 1
prime_numbers = [p for p in range(2, limit + 1) if primes[p]]
return prime_numbers
primes = sieve_of_eratosthenes(100)
print(primes)
2. Sito Atkina
Sito Atkina jest bardziej skomplikowanym algorytmem niż Sito Eratostenesa, ale może być bardziej wydajne dla większych zakresów liczb. Działa poprzez bardziej złożony system oznaczania liczb i eliminacji wielokrotności.
Implementacja Sita Atkina do wyznaczenia liczb pierwszych do 100 w języku Python
def sieve_of_atkin(limit):
if limit < 2:
return []
sieve = [False] * (limit + 1)
for x in range(1, int(limit**0.5) + 1):
for y in range(1, int(limit**0.5) + 1):
n = 4*x**2 + y**2
if n <= limit and (n % 12 == 1 or n % 12 == 5):
sieve[n] ^= True
n = 3*x**2 + y**2
if n <= limit and n % 12 == 7:
sieve[n] ^= True
n = 3*x**2 - y**2
if x > y and n <= limit and n % 12 == 11:
sieve[n] ^= True
for r in range(5, int(limit**0.5) + 1):
if sieve[r]:
for i in range(r*r, limit + 1, r*r):
sieve[i] = False
primes = [2, 3] if limit > 2 else []
primes.extend([a for a in range(5, limit + 1) if sieve[a]])
return primes
primes = sieve_of_atkin(100)
print(primes)
Dokładny opis Sita Atkina->
3. Prosty algorytm sprawdzania podzielności
Prosty algorytm sprawdzania podzielności, który jest używany do wyznaczania liczb pierwszych, działa na zasadzie iteracyjnego sprawdzania, czy dana liczba n jest podzielna przez jakąkolwiek liczbę mniejszą od niej, zaczynając od 2 aż do pierwiastka kwadratowego z n. Algorytm ten jest oparty na fakcie, że jeśli liczba n ma dzielnik większy od swojego pierwiastka kwadratowego, to musi mieć również dzielnik mniejszy od swojego pierwiastka kwadratowego. Dzięki temu możemy ograniczyć liczbę sprawdzeń, co znacząco zwiększa efektywność algorytmu.
Kroki algorytmu
Sprawdzanie małych liczb
- Jeśli n jest mniejsze lub równe 1, nie jest liczbą pierwszą.
- Jeśli n jest równe 2 lub 3, jest liczbą pierwszą.
Eliminacja parzystych liczb i wielokrotności trójki
- Jeśli n jest podzielne przez 2 lub 3, nie jest liczbą pierwszą (chyba że n to 2 lub 3).
Sprawdzanie podzielności przez liczby od 5 do pierwiastka z n
Używamy pętli, która sprawdza liczby w formacie 6k±1 (tj. 5, 7, 11, 13, 17, 19, ...), ponieważ wszystkie liczby pierwsze większe niż 3 są postaci 6k±1. To zmniejsza liczbę sprawdzeń.
- Dla każdej liczby i w formacie 6k±1, sprawdzamy, czy n jest podzielne przez i. Jeśli jest, n nie jest liczbą pierwszą.
Implementacja sprawdzenia podzielności w celu wyznaczenia liczb pierwszych do 100 w języku Python
import math
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
# Wyznaczanie liczb pierwszych do 100
primes = [i for i in range(2, 101) if is_prime(i)]
print(primes)
Liczby pierwsze do 100
Wszystkie powyższe metody powinny zwrócić ten sam zestaw liczb pierwszych do 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Początkowe 10 liczb pierwszych to:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Ostatnie 10 liczb pierwszych do 100 to:
53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Każda z opisanych metod ma swoje zalety i wady, ale wszystkie skutecznie wyznaczają liczby pierwsze do 100.
Implementacja Sita Atkina do wyznaczenia liczb pierwszych do 100 w innych językach programowania
Liczby pierwsze do 100 w języku C++
#include <iostream>
#include <vector>
#include <cmath>
void sieve_of_atkin(int limit) {
std::vector<bool> sieve(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)) {
sieve[n] = !sieve[n];
}
n = 3 * x * x + y * y;
if (n <= limit && n % 12 == 7) {
sieve[n] = !sieve[n];
}
n = 3 * x * x - y * y;
if (x > y && n <= limit && n % 12 == 11) {
sieve[n] = !sieve[n];
}
}
}
for (int r = 5; r * r <= limit; ++r) {
if (sieve[r]) {
for (int i = r * r; i <= limit; i += r * r) {
sieve[i] = false;
}
}
}
if (limit > 2) std::cout << 2 << " ";
if (limit > 3) std::cout << 3 << " ";
for (int a = 5; a <= limit; ++a) {
if (sieve[a]) std::cout << a << " ";
}
std::cout << std::endl;
}
int main() {
sieve_of_atkin(100);
return 0;
}
Liczby pierwsze do 100 w języku Java
import java.util.Arrays;
public class SieveOfAtkin {
public static void sieveOfAtkin(int limit) {
boolean[] sieve = new boolean[limit + 1];
Arrays.fill(sieve, 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)) {
sieve[n] = !sieve[n];
}
n = 3 * x * x + y * y;
if (n <= limit && n % 12 == 7) {
sieve[n] = !sieve[n];
}
n = 3 * x * x - y * y;
if (x > y && n <= limit && n % 12 == 11) {
sieve[n] = !sieve[n];
}
}
}
for (int r = 5; r * r <= limit; r++) {
if (sieve[r]) {
for (int i = r * r; i <= limit; i += r * r) {
sieve[i] = false;
}
}
}
if (limit > 2) System.out.print(2 + " ");
if (limit > 3) System.out.print(3 + " ");
for (int a = 5; a <= limit; a++) {
if (sieve[a]) System.out.print(a + " ");
}
}
public static void main(String[] args) {
sieveOfAtkin(100);
}
}
Liczby pierwsze do 100 w języku JavaScript
function sieveOfAtkin(limit) {
let sieve = new 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)) {
sieve[n] = !sieve[n];
}
n = 3 * x * x + y * y;
if (n <= limit && n % 12 === 7) {
sieve[n] = !sieve[n];
}
n = 3 * x * x - y * y;
if (x > y && n <= limit && n % 12 === 11) {
sieve[n] = !sieve[n];
}
}
}
for (let r = 5; r * r <= limit; r++) {
if (sieve[r]) {
for (let i = r * r; i <= limit; i += r * r) {
sieve[i] = false;
}
}
}
if (limit > 2) console.log(2);
if (limit > 3) console.log(3);
for (let a = 5; a <= limit; a++) {
if (sieve[a]) console.log(a);
}
}
sieveOfAtkin(100);
Komentarze