Простой генератор простых чисел в Python
https://stackoverflow.com/questions/567222
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Может кто-нибудь сказать мне, что я делаю не так с этим кодом?В любом случае он просто печатает «count».Мне просто нужен очень простой генератор простых чисел (ничего особенного).
import math
def main():
count = 3
one = 1
while one == 1:
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
continue
if count % x != 0:
print count
count += 1
Решение
Есть некоторые проблемы:
- Почему вы распечатываете число, если оно не делится на x?Это не значит, что он простой, это означает лишь то, что этот конкретный x его не делит.
continueпереходит к следующей итерации цикла, но вы действительно хотите остановить ее, используяbreak
Вот ваш код с несколькими исправлениями, он печатает только простые числа:
import math
def main():
count = 3
while True:
isprime = True
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break
if isprime:
print count
count += 1
Для более эффективной генерации простых чисел см. «Решето Эрастофена», как предлагали другие.Вот хорошая оптимизированная реализация со множеством комментариев:
# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/
def gen_primes():
""" Generate an infinite sequence of prime numbers.
"""
# Maps composites to primes witnessing their compositeness.
# This is memory efficient, as the sieve is not "run forward"
# indefinitely, but only as long as required by the current
# number being tested.
#
D = {}
# The running integer that's checked for primeness
q = 2
while True:
if q not in D:
# q is a new prime.
# Yield it and mark its first multiple that isn't
# already marked in previous iterations
#
yield q
D[q * q] = [q]
else:
# q is composite. D[q] is the list of primes that
# divide it. Since we've reached q, we no longer
# need it in the map, but we'll mark the next
# multiples of its witnesses to prepare for larger
# numbers
#
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
Обратите внимание, что он возвращает генератор.
Другие советы
def is_prime(num):
"""Returns True if the number is prime
else False."""
if num == 0 or num == 1:
return False
for x in range(2, num):
if num % x == 0:
return False
else:
return True
>> filter(is_prime, range(1, 20))
[2, 3, 5, 7, 11, 13, 17, 19]
Мы получим список всех простых чисел до 20.Я мог бы использовать сито Эратостена, но вы сказали, что хотите что -то очень простое.;)
print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]
ре мощно:
import re
def isprime(n):
return re.compile(r'^1?$|^(11+)\1+$').match('1' * n) is None
print [x for x in range(100) if isprime(x)]
###########Output#############
[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]
def primes(n): # simple Sieve of Eratosthenes
odds = range(3, n+1, 2)
sieve = set(sum([range(q*q, n+1, q+q) for q in odds],[]))
return [2] + [p for p in odds if p not in sieve]
>>> primes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Чтобы проверить, является ли число простым:
>>> 541 in primes(541)
True
>>> 543 in primes(543)
False
Вот простой (Python 2.6.2) решение...что соответствует первоначальному запросу ФП (которому уже шесть месяцев);и должно быть вполне приемлемым решением в любом курсе «Программирование 101»…Отсюда и этот пост.
import math
def isPrime(n):
for i in range(2, int(math.sqrt(n)+1)):
if n % i == 0:
return False;
return n>1;
print 2
for n in range(3, 50):
if isPrime(n):
print n
Этот простой метод «грубой силы» «достаточно быстр» для чисел примерно до 16 000 на современных ПК (на моем компьютере с частотой 2 ГГц это заняло около 8 секунд).
Очевидно, что это можно было бы сделать гораздо эффективнее, не пересчитывая простоту каждого четного числа или каждого кратного 3, 5, 7 и т. д. для каждого отдельного числа...См. Решето Эратосфена (см. реализацию eliben выше) или даже Сито Аткина если вы чувствуете себя особенно смелым и/или сумасшедшим.
Пусть покупатель будет бдителен:Я нуб в питоне.Пожалуйста, не принимайте ничего из того, что я говорю, как евангелие.
На мой взгляд, всегда лучше использовать функциональный подход.
Поэтому я сначала создаю функцию, чтобы выяснить, является ли число простым или нет, а затем использую его в цикле или в другом месте по мере необходимости.
def isprime(n):
for x in range(2,n):
if n%x == 0:
return False
return True
Затем запустите простое понимание списка или выражение-генератор, чтобы получить список простых чисел,
[x for x in range(1,100) if isprime(x)]
Это кажется домашним заданием, поэтому я дам подсказку, а не подробное объяснение.Поправьте меня, если я ошибаюсь.
У вас все в порядке, если вы спасаетесь, когда видите четный делитель.
Но вы печатаете «счет», как только видите четное один число, которое на него не делится.2, например, не делится на 9 без остатка.Но это не делает 9 простым числом.Возможно, вы захотите продолжать, пока не будете уверены нет число в диапазоне совпадает.
(как ответили другие, сито - гораздо более эффективный способ...просто пытаюсь помочь вам понять, почему этот конкретный код не делает то, что вы хотите)
Как насчет этого, если вы хотите вычислить простое число напрямую:
def oprime(n):
counter = 0
b = 1
if n == 1:
print 2
while counter < n-1:
b = b + 2
for a in range(2,b):
if b % a == 0:
break
else:
counter = counter + 1
if counter == n-1:
print b
Еще один простой пример с простой оптимизацией, учитывающей только нечетные числа.Все делается с помощью ленивых потоков (генераторов Python).
Использование:простые числа = список (create_prime_iterator (1, 30))
import math
import itertools
def create_prime_iterator(rfrom, rto):
"""Create iterator of prime numbers in range [rfrom, rto]"""
prefix = [2] if rfrom < 3 and rto > 1 else [] # include 2 if it is in range separately as it is a "weird" case of even prime
odd_rfrom = 3 if rfrom < 3 else make_odd(rfrom) # make rfrom an odd number so that we can skip all even nubers when searching for primes, also skip 1 as a non prime odd number.
odd_numbers = (num for num in xrange(odd_rfrom, rto + 1, 2))
prime_generator = (num for num in odd_numbers if not has_odd_divisor(num))
return itertools.chain(prefix, prime_generator)
def has_odd_divisor(num):
"""Test whether number is evenly divisable by odd divisor."""
maxDivisor = int(math.sqrt(num))
for divisor in xrange(3, maxDivisor + 1, 2):
if num % divisor == 0:
return True
return False
def make_odd(number):
"""Make number odd by adding one to it if it was even, otherwise return it unchanged"""
return number | 1
Вот пустая версия Решета Эратосфена, имеющая как нормальную сложность (ниже, чем сортировка массива длины n), так и векторизацию.
import numpy as np
def generate_primes(n):
is_prime = np.ones(n+1,dtype=bool)
is_prime[0:2] = False
for i in range(int(n**0.5)+1):
if is_prime[i]:
is_prime[i*2::i]=False
return np.where(is_prime)[0]
Тайминги:
import time
for i in range(2,10):
timer =time.time()
generate_primes(10**i)
print('n = 10^',i,' time =', round(time.time()-timer,6))
>> n = 10^ 2 time = 5.6e-05
>> n = 10^ 3 time = 6.4e-05
>> n = 10^ 4 time = 0.000114
>> n = 10^ 5 time = 0.000593
>> n = 10^ 6 time = 0.00467
>> n = 10^ 7 time = 0.177758
>> n = 10^ 8 time = 1.701312
>> n = 10^ 9 time = 19.322478
Оператор continue выглядит неправильно.
Вы хотите начать с 2, потому что 2 — первое простое число.
Вы можете написать «пока True:», чтобы получить бесконечный цикл.
Вам необходимо убедиться, что все возможные делители не делят проверяемое число поровну.В этом случае вы будете печатать проверяемое число в любой момент, когда только один из возможных делителей не делит число поровну.
Кроме того, вы не хотите использовать оператор continue, потому что оператор continue просто заставит его проверять следующий возможный делитель, когда вы уже выяснили, что число не является простым.
Вот что у меня есть:
def is_prime(num):
if num < 2: return False
elif num < 4: return True
elif not num % 2: return False
elif num < 9: return True
elif not num % 3: return False
else:
for n in range(5, int(math.sqrt(num) + 1), 6):
if not num % n:
return False
elif not num % (n + 2):
return False
return True
Это довольно быстро для больших чисел, поскольку он проверяет только уже простые числа на предмет делителей числа.
Теперь, если вы хотите создать список простых чисел, вы можете сделать:
# primes up to 'max'
def primes_max(max):
yield 2
for n in range(3, max, 2):
if is_prime(n):
yield n
# the first 'count' primes
def primes_count(count):
counter = 0
num = 3
yield 2
while counter < count:
if is_prime(num):
yield num
counter += 1
num += 2
использование генераторов здесь может быть желательно для повышения эффективности.
И просто для справки, вместо того, чтобы говорить:
one = 1
while one == 1:
# do stuff
вы можете просто сказать:
while 1:
#do stuff
Вы можете создать список простых чисел, используя понимание списка, довольно элегантным способом.Взято из здесь:
>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
>>> primes = [x for x in range(2, 50) if x not in noprimes]
>>> print primes
>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
def genPrimes():
primes = [] # primes generated so far
last = 1 # last number tried
while True:
last += 1
for p in primes:
if last % p == 0:
break
else:
primes.append(last)
yield last
Аналогично пользователю 107745, но вместо двойного отрицания используется «все» (немного более читабельно, но я думаю, что производительность такая же):
import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]
По сути, он перебирает x в диапазоне (2, 100) и выбирает только те, у которых нет mod == 0 для всех t в диапазоне (2,x)
Другой способ, вероятно, просто заполнять простые числа по ходу дела:
primes = set()
def isPrime(x):
if x in primes:
return x
for i in primes:
if not x % i:
return None
else:
primes.add(x)
return x
filter(isPrime, range(2,10000))
def check_prime(x):
if (x < 2):
return 0
elif (x == 2):
return 1
t = range(x)
for i in t[2:]:
if (x % i == 0):
return 0
return 1
СимПи — это библиотека Python для символьной математики.Он предоставляет несколько функций для генерации простых чисел.
isprime(n) # Test if n is a prime number (True) or not (False).
primerange(a, b) # Generate a list of all prime numbers in the range [a, b).
randprime(a, b) # Return a random prime number in the range [a, b).
primepi(n) # Return the number of prime numbers less than or equal to n.
prime(nth) # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1) # Return the largest prime smaller than n
nextprime(n) # Return the ith prime greater than n
sieve.primerange(a, b) # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes.
Вот некоторые примеры.
>>> import sympy
>>>
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[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]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[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]
Если вы хотите найти все простые числа в диапазоне, вы можете сделать это:
def is_prime(num):
"""Returns True if the number is prime
else False."""
if num == 0 or num == 1:
return False
for x in range(2, num):
if num % x == 0:
return False
else:
return True
num = 0
itr = 0
tot = ''
while itr <= 100:
itr = itr + 1
num = num + 1
if is_prime(num) == True:
print(num)
tot = tot + ' ' + str(num)
print(tot)
Просто добавь while its <= и ваш номер для диапазона.
ВЫХОД:
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
Использование генератора:
def primes(num):
if 2 <= num:
yield 2
for i in range(3, num + 1, 2):
if all(i % x != 0 for x in range(3, int(math.sqrt(i) + 1))):
yield i
Использование:
for i in primes(10):
print(i)
2, 3, 5, 7
import time
maxnum=input("You want the prime number of 1 through....")
n=2
prime=[]
start=time.time()
while n<=maxnum:
d=2.0
pr=True
cntr=0
while d<n**.5:
if n%d==0:
pr=False
else:
break
d=d+1
if cntr==0:
prime.append(n)
#print n
n=n+1
print "Total time:",time.time()-start
Для меня приведенное ниже решение выглядит простым и понятным.
import math
def is_prime(num):
if num < 2:
return False
for i in range(2, int(math.sqrt(num) + 1)):
if num % i == 0:
return False
return True
