Реализации алгоритмов/Решето Эратосфена

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел, не превышающих некоторое натуральное число n.

Реализации

Множество примеров реализации приведено в проекте rosettacode.org. В данном разделе приводится несколько примеров на популярных языках программирования:

C/C++

Обычный вариант

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;

Java

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)

Python 3.x

Вариант № 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 - любое число

См. также

Решето Аткина

Решето Сундарама