Реализации алгоритмов/Решето Эратосфена
Внешний вид
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел, не превышающих некоторое натуральное число n.
Реализации
[править]Множество примеров реализации приведено в проекте rosettacode.org[1]. В данном разделе приводится несколько примеров на популярных языках программирования:
Обычный вариант
[править]int n;
vector<char> prime (n+1, true);
prime[0] = prime[1] = false;
for (int i=2; i<=n; ++i)
if (prime[i])
if (i * 1ll * i <= n) //1ll для перевода в long long
for (int j=i*i; j<=n; j+=i)
prime[j] = false;
Просеивание простыми до корня
[править]int n;
vector<bool> prime (n + 1, true);
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; ++i) // valid for n < 46340^2 = 2147395600
if (prime[i])
for (int j = i * i; j <= n; j += i)
prime[j] = false;
import java.util.Arrays;
public class Eratosfen {
boolean[] primes;
public Eratosfen(int n) {
primes=new boolean[n+1];
}
public void fillSieve() {
Arrays.fill(primes, true);
primes[0] = false;
primes[1] = false;
for (int i = 2; i < primes.length; ++i) {
if (primes[i]) {
for (int j = 2; i * j < primes.length; ++j) {
primes[i * j] = false;
}
}
}
}
}
Haskell
[править]Базисный вариант
[править]primesTo n = eratos [2..n] where
eratos [] = []
eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..n])
minus (x:xs) (y:ys) = case (compare x y) of
LT -> x : minus xs (y:ys)
EQ -> minus xs ys
GT -> minus (x:xs) ys
minus xs _ = xs
Вариация по Эйлеру
[править]primesToEU n = eulers [2..n] where
eulers [] = []
eulers (p:xs) = p : eulers (xs `minus` takeWhile (<= n) (map (p*) (p:xs)))
-- eratos (p:xs) = p : eratos (xs `minus` takeWhile (<= n) (map (p*) [p..] ))
Поэтапная фильтровка проверками на делимость (не Эратосфен; медленно)
[править]primesT = sieve [2..] -- знаменитый код Дейвида Тёрнера
where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0]
Поэтапное решето, с немедленным отсеиванием (медленно)
[править]primesE = sieve [2..]
where
sieve (p:xs) = p : sieve (minus xs [p, p+p..])
-- или:
-- ps = (map head . scanl minus [2..] . map (\p -> [p, p+p..])) ps
С отложенным отсеиванием, от квадратов простых чисел (гораздо быстрее)
[править]primesEQ = 2 : sieve [3..] 4 primesEQ
where
sieve (x:xs) q (p:t)
| x < q = x : sieve xs q (p:t)
| otherwise = sieve (minus xs [q, q+p..]) (head t^2) t
С комбинированным бесконечным решетом, от Richard Bird
[править]primesB = 2 : minus [3..] (foldr (\p r-> (p*p) : union [p*p+p, p*p+2*p..] r)
[] primesB)
union (x:xs) (y:ys) = case (compare x y) of
LT -> x : union xs (y:ys)
EQ -> x : union xs ys
GT -> y : union (x:xs) ys
Просеивание через массив, посегментно между квадратами простых чисел
[править]import Data.Array.Unboxed
ps = 2 : [n | (px, r:q:_) <- zip (inits ps)
(tails (2 : [p^2 | p <- ps]))
, (n, True) <- assocs (
accumArray (\_ _ -> False) True
(r+1,q-1)
[ (n,()) | p <- px
, let s = div (r+p) p * p
, n <- [s, s+p .. q-1] ]
:: UArray Int Bool ) ]
Python 2.x
[править]Функция возвращает список простых и список составных чисел вплоть до заданного n:
def eratosthenes (n):
primes = []
multiples = []
for i in xrange(2, n + 1):
if i not in multiples:
primes.append(i)
multiples.extend(xrange(i * i, n + 1, i))
return (primes, multiples)
Вариант № 1
[править]Функция возвращает список ("решето"), в котором все составные числа заменены нулями:
def eratosthenes(n): # n - число, до которого хотим найти простые числа
sieve = list(range(n + 1))
sieve[1] = 0 # без этой строки итоговый список будет содержать единицу
for i in sieve:
if i > 1:
for j in range(2*i, len(sieve), i):
sieve[j] = 0
return sieve
Вариант № 2
[править]n = int(input()) # число, до которого хотим найти простые числа
numbers = list(range(2, n + 1))
for number in numbers:
if number != 0:
for candidate in range(2 * number, n+1, number):
numbers[candidate-2] = 0
print(*list(filter(lambda x: x != 0, numbers))) # выводим простые числа
Вариант № 3 (списковое включение)
[править]Полностью построено на генераторах списков.
n = int(input())
s = [x for x in range(2, n+1) if x not in [i for sub in [list(range(2 * j, n+1, j)) for j in range(2, n // 2)] for i in sub]]
print(s)
Вариант №4
[править]a, n = True, int(input()) #n - число, до которого хотим дойти
for x in range(1,n):
for y in range(1,n):
if x != y and y != 1:
if not x % y:
a = False
break
if a == True:
print(x,end=' ')
a = True
Вариант №5
[править]Решение с множеством set, которое было тут ранее неверное,
но ниже представлено решение, как в первом варианте, только с заменой нулей на пустоту.
def eratosthenes(n): # n - число, до которого хотим найти простые числа
sieve = list(range(n + 1))
sieve[1] = 0 # без этой строки итоговый список будет содержать единицу
for i in sieve:
if i > 1:
for j in range(i + i, len(sieve), i):
sieve[j] = 0
sieve1 = [x for x in sieve if x != 0]
return sieve1
print(eratosthenes(n)) #где n - любое число