Реализации алгоритмов/Решето Эратосфена: различия между версиями

Содержимое удалено Содержимое добавлено
перенесено из w:Решето Эратосфена
(нет различий)

Версия от 14:39, 15 марта 2015

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

С / С++

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;
int n;
boolean[] primes=new boolean[n];
public void fillSieve() {
    Arrays.fill(primes,true);
    primes[0]=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;
            }
        }
    }
}

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

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

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

Python 3.x

n = int(input())    # число, до которого хотим найти простые числа 
s = list(range(n))
for i in s[2:]:
    for j in range(2*i,n,i):
            s[j]=0
print(*list(filter(lambda x: x!=0,s)))    # выводим простые числа

Python 3.x (списковое включение)

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

n = int(input())
s = [x for x in range(1,n) if x not in [i for sub in [list(range(2*j,n,j)) for j in range(2,n//2)] for i in sub]]
print(*s)

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

Примечания