Простой простой генератор в Python

Question

Не мог бы кто-нибудь рассказать мне, что я делаю неправильно с этим кодом? Это просто печать «счет». Мне просто нужен простой простой генератор (ничего необычного).

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 

Answer 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 

Для более эффективного простого поколения, см сито Erastothenes, как и другие предложили. Вот хорошая, оптимизированная реализация с большим количеством комментариев:

# 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 

Обратите внимание, что он возвращает генератор.

Answer 2

• продолжени заявление выглядит неправильно.

• Вы хотите начать с 2, потому что 2 - первое простое число.

• Вы можете написать «while True:», чтобы получить бесконечный цикл.

Answer 3

Это кажется домашним заданием-y, поэтому я дам подсказку, а не подробное объяснение. Поправьте меня, если я ошибаюсь.

Вы отлично справляетесь с спасением, когда видите четный делитель.

Но вы печатаете «счет», как только видите, один номер, который не делит на него. 2, например, не делится равномерно на 9. Но это не делает 9 простым. Возможно, вам захочется продолжать, пока вы не уверены, что нет номер в совпадении.

(как другие ответили, решето является гораздо более эффективным способом пойти ... просто пытаюсь помочь вам понять, почему этот конкретный код не делает то, что вы хотите)

Answer 4

Вы должны убедиться, что все возможные делители не равномерно делят число, которое вы проверяете. В этом случае вы будете печатать номер, который вы проверяете в любой момент, только один из возможных делителей не равномерно делит число.

Также вы не хотите использовать оператор continue, потому что continue просто заставит его проверить следующий возможный делитель, если вы уже узнали, что число не является простым.

Answer 5

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 в списке. Я мог бы использовать Сито Эратосфена, но ты сказал что-то очень простое.;)

Answer 6

Вот что у меня есть:

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 

Answer 7

Вы можете создать список простых чисел, используя списочные в довольно элегантной манере. Взятые из here:

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

Answer 8

Вот простой (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 и т. Д. Для каждого отдельного номера ... См. Sieve of Eratosthenes (см. Реализацию eliben выше), или даже Sieve of Atkin, если вы чувствуете себя особенно смелыми и/или сумасшедшими.

Caveat Emptor: Я python noob. Пожалуйста, не принимайте ничего, что я говорю как Евангелие.

Answer 9

print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]] 

Answer 10

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 

Answer 11

Как об этом, если вы хотите, чтобы вычислить простое непосредственно:

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 

Answer 12

На мой взгляд, это всегда лучше взять функциональный подход,

Так я создаю прежде всего, чтобы узнать, является ли число простым или нет, тогда используйте его в цикле или в другом месте по мере необходимости.

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

Answer 13

Подобно user107745, но используя «все» вместо двойного отрицания (немного более удобными для чтения, но я думаю, что такую ​​же производительность):

import math 
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))] 

в основном это перебирает х в диапазоне (2, 100) и выбирать только те, которые не имеют мод == 0 для всех т в диапазоне (2, х)

Другой способ, вероятно, просто заселение простые числа, как мы идем:

Answer 14

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 

Answer 15

Еще один простой пример, с простой оптимизации только с учетом нечетные числа. Все сделано с ленивыми потоками (генераторы питона).

Использование: простые числа = список (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 

Answer 16

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 

Answer 17

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 

Answer 18

вновь является мощным:

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] 

Answer 19

Для меня решение ниже выглядит просто и легко следовать.

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 

Answer 20

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]