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

From Викиучебник
Jump to navigation Jump to search

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

Реализации[edit]

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

C/C++[edit]

Обычный вариант[edit]

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;

Просеивание простыми до корня[edit]

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[edit]

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[edit]

Базисный вариант[edit]

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

Вариация по Эйлеру[edit]

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..] ))

Поэтапная фильтровка проверками на делимость (не Эратосфен; медленно)[edit]

primesT = sieve [2..]         -- знаменитый код Дейвида Тёрнера
          where  
          sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0]

Поэтапное решето, с немедленным отсеиванием (медленно)[edit]

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

С отложенным отсеиванием, от квадратов простых чисел (гораздо быстрее)[edit]

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[edit]

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

Просеивание через массив, посегментно между квадратами простых чисел[edit]

import Data.Array

ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2)) ps (inits ps),
              (n,True)    <- assocs (
                                accumArray (\_ _ -> False) True (r+1,q-1)
                         [(m,()) | p <- px, 
                                   let s=(r+p)`div`p*p, m <- [s, s+p..q-1]] )]

Python 2.x[edit]

Функция возвращает список простых и список составных чисел вплоть до заданного 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[edit]

Вариант № 1[edit]

Функция возвращает список ("решето"), в котором все составные числа заменены нулями:

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
    return sieve

Вариант № 2[edit]

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 (списковое включение)[edit]

Полностью построено на генераторах списков.

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[edit]

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[edit]

С использованием множества set
import math
N = int(input())
def p(N):
    s = set(range(1, N, 2))
    for i in range(2, int(math.sqrt(N))):
        if i in s: 
            s -= set(range(i*i, N, i))
    return s
print(p(N))

См. также[edit]

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

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

Примечания[edit]