Реализации алгоритмов/Решето Эратосфена: различия между версиями
Содержимое удалено Содержимое добавлено
РоманСузи (обсуждение | вклад) перенесено из 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