Ctrl →

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))

Отредактировано FishHook (Окт. 9, 2015 12:32:05)

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]

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. Хотя скорость значительно проседает.

Отредактировано noob_saibot (Окт. 9, 2015 13:41:48)

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]
>>>

Отредактировано py.user.next (Окт. 10, 2015 04:03:00)

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

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

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

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

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

Python-сообщество

Уведомления

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

Нахождение простых чисел

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

Нахождение простых чисел

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

Нахождение простых чисел

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

Нахождение простых чисел

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

Нахождение простых чисел

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

Нахождение простых чисел

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

Нахождение простых чисел

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

Нахождение простых чисел

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

Нахождение простых чисел

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

Нахождение простых чисел

Board footer