Печать последовательных простых чисел - PullRequest
Новая
       8

Печать последовательных простых чисел

0 голосов
/ 24 августа 2018

Я пытаюсь создать программу на Python, которая печатает последовательные простые числа. 

estPrimes = [2, 3]
num = 3
run = True

while run == True:
    for i in range(estPrimes[0], estPrimes[(len(estPrimes) - 1)]):
        if i % num == 0:
            num += 2
            sleep(1)
        else:
            estPrimes.append(num)
            print(num)
            sleep(1)
            num += 2

Это закончится печатью только по двое, я знаю, что это как-то связано с num += 2, но,почему он не делится на список estPrimes?

1 Ответ

0 голосов
/ 24 августа 2018

С чего начать?

  • Вы редактируете список, перебирая его. Это вообще плохо посоветовал - из этого могут получиться странные ошибки.

  • Вы увеличиваете num независимо от того, что происходит в вашем состоянии - это ваша основная проблема

  • вы проверяете каждое число между первым и последним найденными простыми числами, а не только простые числа

вот исправление вашего кода 

def print_primes_to(n):

    primes = [2,3]
    for prime in primes:
        print(prime)

    for num in range(5, n, 2):
        isprime = True
        for prime in primes:
            if num % prime == 0: #not prime
                isprime = False
                break
        if isprime:  # could replace with for/else
            primes.append(num)
            print(num)

контрольный пример 

>>> print_primes_to(30)
2
3
5
7
11
13
17
19
23
29

Есть лучшие алгоритмы, вот один, который у меня есть: 

import itertools as _itertools

def primelist(n):
    """Returns a list of all primes less than n."""
    if n <= 2:
        return []
    nums = [True]*(n - 2)
    for num in range(2, _rootp1(n)):
        for counter in _itertools.count(num):
            product = counter * num
            if product >= n:
                break
            nums[product - 2] = False
    return [index for index, val in enumerate(nums, 2) if val]

def _rootp1(n: float) -> int:
    """returns the truncated square root of n plus 1 for use in range"""
    return int(n**0.5) + 1

Посмотрите, сколько нужно времени, чтобы сгенерировать все простые числа менее 1 миллиона 

%timeit primelist(1_000_000)  
1.33 s ± 30.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
...