Реализации алгоритмов/Решето Эратосфена: различия между версиями
Содержимое удалено Содержимое добавлено
м →Haskell: дополнение, уточнение, обновление данных |
Добавлены ссылки на Решето Аткина и Сундарама; поправлено форматирование |
||
Строка 1:
{{wikipedia|Решето Эратосфена}}
=Реализации=
Множество примеров реализации приведено в проекте rosettacode.org<ref>[http://rosettacode.org/wiki/Sieve_of_Eratosthenes Реализация метода на различных языках программирования]</ref>. В данном разделе приводится несколько примеров на популярных языках программирования:
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
<source lang="cpp">
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;
</source>
==
<source lang="java">
import java.util.Arrays;
int n;
boolean[] primes = new boolean[n + 1];
public void fillSieve() {
Arrays.fill(primes, true);
primes[0] = primes[1] = false;
for (int i = 2; i < primes.length;
if (primes[i]) {
for (int j = 2; i * j < primes.length;
primes[i * j] = false;
}
}
Строка 33 ⟶ 37 :
</source>
==
===Базисный вариант===
<source lang="haskell">
primesTo n = eratos [2..n] where
Строка 91 ⟶ 51 :
</source>
===Вариация по типу Эйлера
<source lang="haskell">
primesToEU n = eulers [2..n] where
Строка 100 ⟶ 60 :
</source>
===Медленный вариант, с использованием функционала filter
<source lang="haskell">
primesOf n = helper [2..n] where
Строка 108 ⟶ 68 :
filt a lst = filter (\x -> (mod x a) /= 0) lst
</source>
===Неограниченное решето===
С немедленным отсеиванием (медленно):
<source lang="haskell">
Строка 119 ⟶ 78 :
</source>
===С отложенным отсеиванием, от квадратов простых чисел (гораздо быстрее)
<source lang="haskell">
primesEQ = 2 : sieve [3..] 4 primesEQ
Строка 128 ⟶ 87 :
</source>
===С комбинированным решетом, от Richard Bird
<source lang="haskell">
primesB = 2 : minus [3..] (foldr (\p r-> (p*p) : union [p*p+p,p*p+2*p..] r)
Строка 140 ⟶ 98 :
</source>
==Python 2.x==
Функция возвращает список простых и список составных чисел вплоть до заданного ''n'':
<source lang="python">
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)
</source>
==[[w:Python|Python 3.x]]==
===Вариант № 1===
Функция возвращает список ("''решето''"), в котором все составные числа заменены нулями:
<source lang="python">
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
</source>
===Вариант № 1===
<source lang="python">
n = int(input()) # число, до которого хотим найти простые числа
numbers = list(range(2, n + 1))
for number in numbers:
for candidate in range(2 * number, n, number):
numbers[candidate] = 0
print(*list(filter(lambda x: x != 0, numbers))) # выводим простые числа
</source>
===Вариант № 3 (списковое включение)===
Полностью построено на генераторах списков.
<source lang="python">
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)
</source>
=См. также=
[[Реализации алгоритмов/Решето Аткина|Решето Аткина]]
[[Реализации алгоритмов/Решето Сундарама|Решето Сундарама]]
=Примечания=
{{примечания}}
| |||