For reference, there’s a pretty significant speed difference between the various stated solutions. Here is some comparison code. The solution pointed to by Lennart is called «historic», the one proposed by Ants is called «naive», and the one by RC is called «regexp.»
from sys import argv
from time import time
def prime(i, primes):
for prime in primes:
if not (i == prime or i % prime):
return False
primes.add(i)
return i
def historic(n):
primes = set([2])
i, p = 2, 0
while True:
if prime(i, primes):
p += 1
if p == n:
return primes
i += 1
def naive(n):
from itertools import count, islice
primes = (n for n in count(2) if all(n % d for d in range(2, n)))
return islice(primes, 0, n)
def isPrime(n):
import re
# see http://tinyurl.com/3dbhjv
return re.match(r'^1?$|^(11+?)1+$', '1' * n) == None
def regexp(n):
import sys
N = int(sys.argv[1]) # number of primes wanted (from command-line)
M = 100 # upper-bound of search space
l = list() # result list
while len(l) < N:
l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
M += 100 # increment upper-bound
return l[:N] # print result list limited to N elements
def dotime(func, n):
print func.__name__
start = time()
print sorted(list(func(n)))
print 'Time in seconds: ' + str(time() - start)
if __name__ == "__main__":
for func in naive, historic, regexp:
dotime(func, int(argv[1]))
The output of this on my machine for n = 100 is:
naive
[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]
Time in seconds: 0.0219371318817
historic
[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]
Time in seconds: 0.00515413284302
regexp
[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]
Time in seconds: 0.0733318328857
As you can see, there’s a pretty big discrepancy. Here it is again for 1000 (prime outputs removed):
naive
Time in seconds: 1.49018788338
historic
Time in seconds: 0.148319005966
regexp
Time in seconds: 29.2350409031
Алгоритм нахождения простых чисел
Время на прочтение
3 мин
Количество просмотров 432K
Оптимизация алгоритма нахождения простых чисел
2 3 5 7 11 13 17 19 23 29 31… $250.000…
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
# Листинг 1
# вводим N
n = input("n=")
# создаем пустой список для хранения простых чисел
lst = []
# в k будем хранить количество делителей
k = 0
# пробегаем все числа от 2 до N
for i in xrange(2, n+1):
# пробегаем все числа от 2 до текущего
for j in xrange(2, i):
# ищем количество делителей
if i % j == 0:
k = k + 1
# если делителей нет, добавляем число в список
if k == 0:
lst.append(i)
else:
k = 0
# выводим на экран список
print lst
Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.
# Листинг 2
n = input("n=")
lst = []
for i in xrange(2, n+1):
for j in xrange(2, i):
if i % j == 0:
# если делитель найден, число не простое.
break
else:
lst.append(i)
print lst
Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.
# Листинг 3
n = input("n=")
lst=[]
for i in xrange(2, n+1):
# пробегаем по списку (lst) простых чисел
for j in lst:
if i % j == 0:
break
else:
lst.append(i)
print lst
А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.
# Листинг 4
from math import sqrt
n = input("n=")
lst=[]
for i in xrange(2, n+1):
for j in lst:
if j > int((sqrt(i)) + 1):
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst
Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.
# Листинг 5
from math import sqrt
n = input("n=")
lst=[]
for i in xrange(2, n+1):
if (i > 10):
if (i%2==0) or (i%10==5):
continue
for j in lst:
if j > int((sqrt(i)) + 1):
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst
В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:
# Листинг 6
from math import sqrt
n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
if (i > 10) and (i%10==5):
continue
for j in lst:
if j > int((sqrt(i)) + 1):
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst
Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.
P.S.
Благодаря замечаниям получаем Листинг 7:
# Листинг 7
n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
if (i > 10) and (i%10==5):
continue
for j in lst:
if j*j-1 > i:
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst
при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053
Решето Эратосфена:
# Листинг 8
n = input("n=")
a = range(n+1)
a[1] = 0
lst = []
i = 2
while i <= n:
if a[i] != 0:
lst.append(a[i])
for j in xrange(i, n+1, i):
a[j] = 0
i += 1
print lst
Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2422000; 2422080], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку.
мой способ дает бесконечное выполнение программы
for x in range(2422000, 2422080):
a = []
for n in range(1,x):
if x%n==0 and (x==n or n==1):
a.append(n)
print(a)
Эникейщик
25.1k7 золотых знаков30 серебряных знаков46 бронзовых знаков
задан 19 дек 2020 в 21:39
4
По идее как то так
a = []
for x in range(2422000, 2422080):
d = 2
while x % d != 0:
d += 1
if d == x:
a.append(x)
print(a)
ответ дан 19 дек 2020 в 22:18
KersKers
3,1562 золотых знака7 серебряных знаков16 бронзовых знаков
Попробуйте так:
import math
def is_prime(i):
m = min(i, int(math.sqrt(b)))
l = range(2, m)
r = map(lambda x: i % x == 0, l)
return not any(r)
a = 2422000
b = 2422080
ls = range(a, b)
_list = list(filter(is_prime, ls))
print(*[ f'{i+1}: {v}' for i, v in enumerate(_list)], sep='n')
ответ дан 19 дек 2020 в 22:18
S. NickS. Nick
70.2k96 золотых знаков36 серебряных знаков55 бронзовых знаков
1
Под словами «номер по порядку» имеется в виду номер в списке (2422000, 2422080), или номер числа в списке простых чисел? Если первый вариант, то решение такое:
for i in range(2422000, 2422081):
for j in range(2, i // 2):
if i % j == 0: break
else: print(i - 2421999, i)
ответ дан 19 дек 2020 в 21:45
Попробуйте через списковую сборку, в первом списке поставьте нужный интервал в range(2, 1001)…, числа до 1000 поставил для примера,
вот:
print([x for x in range(2, 1001) if not [n for n in range(2, x) if not x % n]])
или
print([x for x in range(2, 1001) if all(x % t for t in range(2, int(math.sqrt(x))+1))])
ответ дан 13 июн 2021 в 19:39
PoMaXaPoMaXa
12 бронзовых знака
1
for i in range(2422000, 2422081):
deli=[]
for a in range(2,i+1):
if i%a==0:
deli.append(a)
if len(deli)>1:
break
if len(deli)==1:
print(deli)
ответ дан 23 июн 2021 в 10:14
1
Простое число — это натуральное число, которое больше 1 и не имеет положительного делителя, кроме 1 и самого себя, например 2, 3, 5, 7, 11, 13 и так далее.
Пользователю даются два целых числа, нижнее значение и верхнее значение. Задача состоит в том, чтобы написать программу Python для вывода всех простых чисел в заданном интервале (или диапазоне).
Чтобы напечатать все простые числа в заданном интервале, пользователь должен выполнить следующие шаги:
- Шаг 1: Переберите все элементы в заданном диапазоне.
- Шаг 2: Проверьте для каждого числа, есть ли у него какой-либо множитель между 1 и самим собой.
- Шаг 3: Если да, то число не простое, и оно перейдет к следующему числу.
- Шаг 4: Если нет, то это простое число, и программа распечатает его и проверит следующее число.
- Шаг 5: Цикл прервется, когда будет достигнуто верхнее значение.
Пример: код Python для печати простого числа в заданном интервале.
# First, we will take the input:
lower_value = int(input("Please, Enter the Lowest Range Value: "))
upper_value = int(input("Please, Enter the Upper Range Value: "))
print("The Prime Numbers in the range are: ")
for number in range(lower_value, upper_value + 1):
if number > 1:
for i in range(2, number):
if(number % i) == 0:
break
else:
print(number)
Выход:
Please, Enter the Lowest Range Value: 14 Please, Enter the Upper Range Value: 97 The Prime Numbers in the range are: 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Заключение
В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.
Изучаю Python вместе с вами, читаю, собираю и записываю информацию опытных программистов.
Здесь простая и интуитивно понятная версия проверки того, является ли это простым в функции RECURSIVE!:) (Я сделал это как домашнее задание для класса MIT)
В python он работает очень быстро до 1900 года. Если вы попробуете более 1900, вы получите интересную ошибку:) (Хотелось бы узнать, сколько номеров может контролировать ваш компьютер?)
def is_prime(n, div=2):
if div> n/2.0: return True
if n% div == 0:
return False
else:
div+=1
return is_prime(n,div)
#The program:
until = 1000
for i in range(until):
if is_prime(i):
print i
Конечно… если вам нравятся рекурсивные функции, этот небольшой код может быть обновлен со словарем, чтобы серьезно увеличить его производительность и избежать этой смешной ошибки.
Здесь просто обновление уровня 1 с интеграцией MEMORY:
import datetime
def is_prime(n, div=2):
global primelist
if div> n/2.0: return True
if div < primelist[0]:
div = primelist[0]
for x in primelist:
if x ==0 or x==1: continue
if n % x == 0:
return False
if n% div == 0:
return False
else:
div+=1
return is_prime(n,div)
now = datetime.datetime.now()
print 'time and date:',now
until = 100000
primelist=[]
for i in range(until):
if is_prime(i):
primelist.insert(0,i)
print "There are", len(primelist),"prime numbers, until", until
print primelist[0:100], "..."
finish = datetime.datetime.now()
print "It took your computer", finish - now , " to calculate it"
Вот резули, где я напечатал последние 100 простых чисел.
время и дата: 2013-10-15 13: 32: 11.674448
Есть 9594 простых чисел, до 100000
[99991, 99989, 99971, 99961, 99929, 99923, 99907, 99901, 99881, 99877, 99871, 99859, 99839, 99833, 99829, 99823, 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719, 99713, 99709, 99707, 99689, 99679, 99667, 99661, 99643, 99623, 99611, 99607, 99581, 99577, 99571, 99563, 99559, 99551, 99529, 99527, 99523, 99497, 99439, 99431, 99409, 99401, 99397, 99391, 99377, 99371, 99367, 99349, 99347, 99317, 99289, 99277, 99259, 99257, 99251, 99241, 99233, 99223, 99191, 99181, 99173, 99137, 99133, 99131, 99119, 99109, 99103, 99089, 99083, 99079, 99053, 99041, 99023, 99017, 99013, 98999, 98993, 98981, 98963, 98953, 98947, 98939, 98929, 98927, 98911, 98909, 98899, 98897]…
Для его вычисления потребовался ваш компьютер 0: 00: 40.871083.
Так что для моего ноутбука i7 потребовалось 40 секунд, чтобы вычислить его.:)