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

Question

Может кто-нибудь сказать мне, что я делаю не так с этим кодом? В любом случае, это просто печать '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

Answer 1

Есть некоторые проблемы:

• Почему вы распечатываете счет, если он не делится на 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

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

Answer 2

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 3

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

Answer 4

ре мощно:

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 5

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 6

Вот решение simple (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 на современных ПК (на моем устройстве с частотой 2 ГГц это заняло около 8 секунд).

Очевидно, что это можно сделать гораздо эффективнее, не пересчитывая простоту каждого четного числа или каждого кратного 3, 5, 7 и т. Д. Для каждого отдельного числа ... См. Сито Эратосфена (см. Реализацию eliben выше) или даже Сито Аткина , если вы чувствуете себя особенно смелым и / или сумасшедшим.

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

Answer 7

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

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

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 8

Вот небольшая версия Sieve of Eratosthenes, имеющая как нормальную сложность (ниже, чем сортировка массива длины 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

Answer 9

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

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

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

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

Answer 10

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

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