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

Содержимое удалено Содержимое добавлено
м <source> -> <syntaxhighlight> (phab:T237267)
Строка 7:
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
=== Обычный вариант ===
<sourcesyntaxhighlight lang="cpp">
int n;
vector<char> prime (n+1, true);
Строка 16:
for (int j=i*i; j<=n; j+=i)
prime[j] = false;
</syntaxhighlight>
</source>
 
=== Просеивание простыми до корня ===
<sourcesyntaxhighlight lang="cpp">
int n;
vector<bool> prime (n + 1, true);
Строка 27:
for (int j = i * i; j <= n; j += i)
prime[j] = false;
</syntaxhighlight>
</source>
 
==[[w:Java|Java]]==
<sourcesyntaxhighlight lang="java">
import java.util.Arrays;
 
Строка 52:
}
}
</syntaxhighlight>
</source>
 
==Haskell==
===Базисный вариант===
<sourcesyntaxhighlight lang="haskell">
primesTo n = eratos [2..n] where
eratos [] = []
Строка 66:
GT -> minus (x:xs) ys
minus xs _ = xs
</syntaxhighlight>
</source>
 
===Вариация по Эйлеру===
<sourcesyntaxhighlight lang="haskell">
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..] ))
</syntaxhighlight>
</source>
 
===Поэтапная фильтровка проверками на делимость (не Эратосфен; медленно)===
<sourcesyntaxhighlight lang="haskell">
primesT = sieve [2..] -- знаменитый код Дейвида Тёрнера
where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0]
</syntaxhighlight>
</source>
 
===Поэтапное решето, с немедленным отсеиванием (медленно)===
<sourcesyntaxhighlight lang="haskell">
primesE = sieve [2..]
where
Строка 90:
-- или:
-- ps = (map head . scanl minus [2..] . map (\p -> [p, p+p..])) ps
</syntaxhighlight>
</source>
 
===С отложенным отсеиванием, от квадратов простых чисел (гораздо быстрее)===
<sourcesyntaxhighlight lang="haskell">
primesEQ = 2 : sieve [3..] 4 primesEQ
where
Строка 99:
| x < q = x : sieve xs q (p:t)
| otherwise = sieve (minus xs [q, q+p..]) (head t^2) t
</syntaxhighlight>
</source>
 
===С комбинированным бесконечным решетом, от Richard Bird===
<sourcesyntaxhighlight lang="haskell">
primesB = 2 : minus [3..] (foldr (\p r-> (p*p) : union [p*p+p, p*p+2*p..] r)
[] primesB)
Строка 110:
EQ -> x : union xs ys
GT -> y : union (x:xs) ys
</syntaxhighlight>
</source>
 
===Просеивание через массив, посегментно между квадратами простых чисел===
<sourcesyntaxhighlight lang="haskell">
import Data.Array
 
Строка 121:
[(m,()) | p <- px,
let s=(r+p)`div`p*p, m <- [s, s+p..q-1]] )]
</syntaxhighlight>
</source>
 
==Python 2.x==
Функция возвращает список простых и список составных чисел вплоть до заданного ''n'':
<sourcesyntaxhighlight lang="python">
def eratosthenes (n):
primes = []
Строка 134:
multiples.extend(xrange(i * i, n + 1, i))
return (primes, multiples)
</syntaxhighlight>
</source>
 
==[[w:Python|Python 3.x]]==
===Вариант № 1===
Функция возвращает список ("''решето''"), в котором все составные числа заменены нулями:
<sourcesyntaxhighlight lang="python">
def eratosthenes(n): # n - число, до которого хотим найти простые числа
sieve = list(range(n + 1))
Строка 148:
sieve[j] = 0
return sieve
</syntaxhighlight>
</source>
 
===Вариант № 2===
<sourcesyntaxhighlight lang="python">
n = int(input()) # число, до которого хотим найти простые числа
numbers = list(range(2, n + 1))
Строка 159:
numbers[candidate-2] = 0
print(*list(filter(lambda x: x != 0, numbers))) # выводим простые числа
</syntaxhighlight>
</source>
 
===Вариант № 3 (списковое включение)===
Полностью построено на генераторах списков.
<sourcesyntaxhighlight lang="python">
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)
</syntaxhighlight>
</source>
 
=== Вариант №4 ===
Строка 184:
 
=== Вариант №5 ===
<sourcesyntaxhighlight lang="python">
Решение с множеством set, которое было тут ранее неверное,
но ниже представлено решение, как в первом варианте, только с заменой нулей на пустоту.
Строка 199:
 
print(eratosthenes(n)) #где n - любое число
</syntaxhighlight>
</source>
 
=См. также=