БГ
Как максимум: строить решето Эратосфена размером √p, при построении решета сразу проверять делимость и если делимо без остатка то return False
При использовании решета это в принципе оптимальный и наиболее шустрый вариант
Size: a a a
2020 May 04
I
Новый вопрос в форуме: Нужна помочь!
VK
При использовании решета это в принципе оптимальный и наиболее шустрый вариант
решето удобно, если надо все простые числа допустим узнать. мне надо просто узнать простое или нет.
VK
При использовании решета это в принципе оптимальный и наиболее шустрый вариант
сейчас проверяет примерно 1000 чисел в секунду
VK
надо проверить 2 миллиона чисел)
БГ
решето удобно, если надо все простые числа допустим узнать. мне надо просто узнать простое или нет.
Падажжи, ты не вкурил фишку
БГ
Как максимум: строить решето Эратосфена размером √p, при построении решета сразу проверять делимость и если делимо без остатка то return False
Перечитай ещё раз
VK
Падажжи, ты не вкурил фишку
чет не вкуриваю все-равно) пойду учить про решето
БГ
чет не вкуриваю все-равно) пойду учить про решето
Смари
AT
def isprime(n):
if n in (2, 3): return True
if n < 2 or n%2 == 0 or n%3 == 0: return False
if n < 9: return True
for x in range(5, int(n**0.5)+1, 6):
if n % x == 0 or n % (x + 2) == 0:
return False
return True
че-то такое по следам СО
VK
def isprime(n):
if n in (2, 3): return True
if n < 2 or n%2 == 0 or n%3 == 0: return False
if n < 9: return True
for x in range(5, int(n**0.5)+1, 6):
if n % x == 0 or n % (x + 2) == 0:
return False
return True
че-то такое по следам СО
интересная реализация)
VK
я походу вкурил че я не так делал
VK
список делителей не обязательно создавать жеж
БГ
чет не вкуриваю все-равно) пойду учить про решето
Берёшь своё число.
Берёшь от него корень (ну логично что дальше искать бессмысленно)
Начинаешь делать решето Эратосфена. При очередном шаге решета проверяешь делимость p на найденное очередное. Если делится - return False, иначе - продолжаешь.
Берёшь от него корень (ну логично что дальше искать бессмысленно)
Начинаешь делать решето Эратосфена. При очередном шаге решета проверяешь делимость p на найденное очередное. Если делится - return False, иначе - продолжаешь.
VK
Берёшь своё число.
Берёшь от него корень (ну логично что дальше искать бессмысленно)
Начинаешь делать решето Эратосфена. При очередном шаге решета проверяешь делимость p на найденное очередное. Если делится - return False, иначе - продолжаешь.
Берёшь от него корень (ну логично что дальше искать бессмысленно)
Начинаешь делать решето Эратосфена. При очередном шаге решета проверяешь делимость p на найденное очередное. Если делится - return False, иначе - продолжаешь.
все я вкурил +-
RO
А я тупанул)
VK
тут каждая 3-я задача про простые числа, есть смысл нормально функцию написать, а не абы как
БГ
Само по себе решето у меня на телефоне изи строило до 10млн, дальше вылетало по памяти. Соответственно учитывая что мы строим до корня то на том же девайсе будет максималка для p равна (10млн)**2 = 10**14.
БГ
На компе - ещё больше, офк
VK
ну это алгоритмы учить надо