Произвольно выбранное число, не превышающее 10^5, с вероятностью 90% составное. Дальше - больше.
Тем не менее, откройте ваш способ.
UPDATE
def main(*mods):
lo = 10 ** 5
hi = 10 ** 9
sieve = [1] * hi
sieve[0] = sieve[1] = 0
for i in range(int(hi ** 0.5) + 1):
if sieve[i]:
for j in range(i * i, hi, i):
sieve[j] = 0
primes = sum(sieve[lo:])
for mod in mods:
counter = [0] * 4
for i in range(lo, hi):
counter[sieve[i] * 2 + sieve[i % mod]] += 1
print('\n{:>17n}\nprime \ check 0 1\n'
' 0 {:7.3f} {:7.3f}\n'
' 1 {:7.3f} {:7.3f}\n'.format(
mod, *[float(i) / primes for i in counter]))
main(30029, 30030, 30047)
30029
prime \ check 0 1
0 16.650 2.019
1 0.892 0.108
30030
prime \ check 0 1
0 17.104 1.564
1 0.437 0.563
30047
prime \ check 0 1
0 16.650 2.018
1 0.892 0.108
Итак, имеем:
По замечанию
Mrrl, знаменатель 30030 действительно подходит гораздо больше своих ближайших простых соседей. И всё же, даёт ли алгоритм какой-то выигрыш?
С одной стороны, он отбрасывает почти половину (0.437) простых, ошибочно объявляя их составными.
Но если этот фильтр вставить в реальный криптоалгоритм, он лишь ухудшит криптостойкость - половина простых известного вида будет выброшена из рассмотрения.
С другой стороны, на диапазоне lo..hi содержание простых около 5%, а алгоритм выдаёт простые к составным в пропорции более 1:3, что заметно лучше.
С третьей стороны, то, что автор назвал "всего 3 математических операции", выливается в предварительное вычисление сита длинной в 30030 чисел. При потоковом поиске простых это как-будто немного, но можно ли с теми же затратами сделать лучше?
Да, можно:
from itertools import cycle
def MillerRabin(n):
return True # допустим, здесь реализован тест Рабина-Миллера
def getprime(startsfrom):
primes = (2, 3, 5, 7, 11, 13)
mod = 1
for p in primes:
mod *= p # итого mod = 30030
steps, x0 = [], mod - 1
for x in range(mod, x0 + mod + 1):
if all(x % p for p in primes):
steps.append(x - x0)
x0 = x
print(len(steps) / mod) # 0.1918 - мы отсеяли 4/5 чисел
# входного потока, не потеряв ни единого простого.
# по итогу имеем те же 25% простых во входном потоке
# на интервале 10^5..10^9
n = startsfrom // mod * mod - 1
for step in cycle(steps):
n += step
if n > startsfrom and MillerRabin(n):
return n
print(getprime(10 ** 500))
# 10^500+961
Простой
Простой
