Может кто-нибудь, пожалуйста, скажите мне, что я делаю неправильно с этим кодом? Это просто печать "счет". Мне просто нужен простой простой генератор (ничего необычного).
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
Есть некоторые проблемы:
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 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]]
re является мощным:
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) решение... которое соответствует исходному запросу OP (теперь шестимесячный); и должно быть вполне приемлемым решением в любом курсе "программирования 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 на современном ПК (занял около 8 секунд на моем ядре 2 ГГц).
Очевидно, что это можно было бы сделать гораздо эффективнее, не пересчитывая грубость каждого четного числа, или каждый кратный 3, 5, 7 и т.д. для каждого отдельного номера... См. Сито Эратосфена (см. выше реализацию eliben) или даже Сито Аткина, если вы чувствуете себя особенно смелыми и/или сумасшедшими.
Caveat Emptor: Я python noob. Пожалуйста, не принимайте ничего, что я говорю как Евангелие.
На мой взгляд, всегда лучше всего использовать функциональный подход,
Поэтому я сначала создаю функцию, чтобы узнать, является ли число простым или нет, затем используйте его в цикле или в другом месте по мере необходимости.
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)]
Это кажется домашним заданием-y, поэтому я дам подсказку, а не подробное объяснение. Исправьте меня, если я ошибаюсь.
Вы отлично справляетесь с тем, что вы видите четный дивизор.
Но вы печатаете "count", как только увидите даже одно число, которое не делит на него. 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
Еще один простой пример: простая оптимизация только с учетом нечетных чисел. Все сделано с ленивыми потоками (генераторы питона).
Использование: primes = list (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 - первое простое число.
Вы можете написать "while 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 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
Как и для user107745, но используя "все" вместо двойного отрицания (немного более читаемый, но я думаю, что такая же производительность):
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 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
SymPy - это библиотека 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