DjangoBB LoFi version

Начало » Python для новичков » Нахождение простых чисел

1 2

old_monty

Окт. 9, 2015 09:49:33

Для нахождения простых чисел в заданном интервале применяю известный метод “решето Эратосфена”:

L = list(range(2, 1000))
for x in L:
   for y in L[x:]:
      if y % x == 0:        
         L.remove(y)
print(L)

При не очень больших числах (примерно до 10000) работает достаточно быстро. Но вообще вложенные циклы - плохая идея. Можно ли от них избавиться?

FishHook

Окт. 9, 2015 12:31:45

Посмотрите на реализацию, которая на моём компьютере быстрее примерно в 20 раз

def erat1(n):
    L = list(range(2, n))
    for x in L:
       for y in L[x:]:
          if y % x == 0:
             L.remove(y)
    return L
 
import math
def erat2(n):
    a = [True] * n
    for i in range(2, int(math.sqrt(n))):
        for j in range(i * 2, n, i):
            a[j] = False
    b = [i for i in range(2, n) if a[i]]
    return b
 
import timeit
print(timeit.timeit("erat1(1000)", setup="from __main__ import erat1", number=100))
print(timeit.timeit("erat2(1000)", setup="from __main__ import erat2", number=100))

noob_saibot

Окт. 9, 2015 12:57:44

FishHook
Посмотрите на реализацию, которая на моём компьютере быстрее примерно в 20 раз

import math
def erat2(n):
    a = [True] * n
    for i in range(2, int(math.sqrt(n))):
        for j in range(i * 2, n, i):
            a[j] = False
    b = [i for i in range(2, n) if a[i]]
    return b
print erat2(11)

[2, 3, 5, 7, 9]

FishHook

Окт. 9, 2015 13:13:23

Возьмите больший диапазон

FishHook

Окт. 9, 2015 13:16:20

Наверняка какие-то шероховатости нужно подпилить. Вы спрашивали про скорость, вот вам очевидно более быстрый алгоритм, и если вам нужно вы сами дальше его доделаете.

old_monty

Окт. 9, 2015 13:28:17

FishHook
Действительно, работает во много раз быстрее. При n = 1000 примерно в 15 раз на моем компьютере, при n= 10000 быстрее в 93 раза. Но ошибка, на которую указал noob_saibot, тоже есть. Правда, она исчезает уже при n > 15.
В любом случае, спасибо за интересное решение.

noob_saibot

Окт. 9, 2015 13:35:28

import math
def erat2(n):
    a = [True] * n
    for i in range(2, int(math.sqrt(n))):
        for j in range(i * 2, n, i):
            a[j] = False
    b = [i for i in range(2, n) if a[i]]
    return b
print erat2(1000)

961

Может так точнее?

import math
def erat2(n):
    a = [True] * n
    for i in range(2, n/2):
        for j in range(i * 2, n, i):
            a[j] = False
    b = [i for i in range(2, n) if a[i]]
    return b
print erat2(1000)

PS. Хотя скорость значительно проседает.

FishHook

Окт. 9, 2015 22:21:28

Друзья! Коллеги! У вас должен был бы прежде всего возникнуть вопрос, а почему мой алгоритм быстрее? А почему именно в такой прогрессии? Кому нужно готовое решение - только дуракам! Это тривиальная задача, но интересная. Запилить самый быстрый алгоритм - это и есть задача программиста, это самая мякотка профессии.
old_monty, мы от вас ждём оптимального решения

py.user.next

Окт. 10, 2015 03:56:04

old_monty
Правда, она исчезает уже при n > 15.

>>> erat2(35)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31]
>>>

Число 25 - составное.

Подрубим свою древнюю функцию

>>> erat2(1000)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 961, 967, 971, 977, 983, 991, 997]
>>> 
>>> def isprime(x):
...     if x > 3 and x % 2 == 0 or x <= 1:
...         return False
...     for i in range(3, int(x ** 0.5) + 1, 2):
...         if x % i == 0:
...             return False
...     return True
... 
>>> erat2(1000)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 961, 967, 971, 977, 983, 991, 997]
>>> [i for i in _ if not isprime(i)]
[961]
>>>

old_monty

Окт. 10, 2015 09:32:26

FishHook
Друзья! Коллеги! У вас должен был бы прежде всего возникнуть вопрос, а почему мой алгоритм быстрее? А почему именно в такой прогрессии? Кому нужно готовое решение - только дуракам!

Согласен, только дураки пользуются готовыми решениями. Но потом они тебя спрашивают “если ты такой умный, то почему такой бедный?”

FishHook
Это тривиальная задача, но интересная. Запилить самый быстрый алгоритм - это и есть задача программиста, это самая мякотка профессии. old_monty, мы от вас ждём оптимального решения

Готовые примеры более быстрых алгоритмов для простых чисел с анализом сложности и реализацией на псевдокоде можно видеть, например, здесь: https://ru.wikipedia.org/wiki/Решето_Эратосфена.