Для повторения цикла / застрял?Python 3.2

Question

Я пытаюсь написать скрипт на Python для Sieve of Eratosthenes.Я все сделал, но когда я говорю программе, чтобы проверить каждое число, если оно кратно, по крайней мере, одному из простых чисел ниже √input.Все идет хорошо, но когда я пытаюсь удалить мультипликатор, он работает, пока не попытается удалить 6 дважды ... Я просматривал свой код и не могу понять, почему.Я довольно новичок в Python, поэтому помощь будет высоко ценится!--- Обратите внимание, что интервал между кодами отключен из-за способа создания блоков кода SOF:

import math, os, threading

global iswhole
global tdprime

def iswhole(x):
if x%1 == 0:
    return True
else:
    return False

def tdprime(x):
prime = True
n = 2

while n < x:
    if iswhole(x/n) == True:
        return False
        prime = False
        n = x
    else:
        n += 1

if prime == True:
    return True

number = 0

while number != 1:

number = int(input("Enter number to calculate all primes up to:  "))
number_range = range(1,number+1)
sqrt = math.sqrt(number)
rsqrt = round(sqrt)
thelist = []
tsl = []

for num in range(1,rsqrt):
    if tdprime(num) == True:
        tsl.append(num)
tsl.remove(1)

for x in number_range: ## Making the List
    thelist.append(x)
    ## Note it's " Key: Value " in dictionaries

print(tsl)
print("thelist: ",thelist)
print("Square root of input = ",sqrt)
print("Rounded Square root of input = ",rsqrt)
print()

for x in thelist: ## Testing each number in thelist

    multiple = False

    for y in tsl: ## Each prime number under √number

        if iswhole(x/y):
            print(x) ## If the current number in thelist divided by one of the prime numbers under √number is a whole
            thelist.remove(x)## Remove the current number which isn't a prime
            thelist.sort()
            multiple = True ## Make multiple true so it doesn't print (could remove the multiple stuff and other if function, kind of pointless function now)

    if multiple == False:
        print("Prime! ",x)


print(thelist)

Answer 1

Ваш код может быть значительно упрощен следующими реализациями:

• Числа вплоть до числа n могут быть легко сгенерированы по мере необходимости, они недолжны быть вычислены заранее и сохранены в списке.

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

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

Попробуйте что-то вроде этого:

stop = int(input("Enter number to calculate all primes up to: "))

primes = []

for n in range(3, stop, 2): # Step by two each time
    was_prime = True # Needed to break out of nested loop
    for p in primes:
        if n % p == 0: # A prime divides n
             was_prime = False
             break # No need to continue
    if was_prime:
        primes.append(n)

print(primes) # You can insert the number 2 here if you like

Также обратите внимание на интервалы и отступы.В Python, когда вы неправильно указали интервал, его не только трудно прочитать, но и ошибка времени выполнения.

Answer 2

Я вижу проблему с этим битом:

for x in thelist: ## Testing each number in thelist

    multiple = False

    for y in tsl: ## Each prime number under √number

        if iswhole(x/y):
            print(x) ## If the current number in thelist divided by one of the prime numbers under √number is a whole
            thelist.remove(x)## Remove the current number which isn't a prime
            thelist.sort()

Вы вызываете thelist.remove(x) и thelist.sort() во время итерации по thelist.Как правило, вы не хотите изменять структуру, которую вы повторяете в Python.Обычно это путает внутренний механизм, выполняющий итерацию;у вас появляются такие симптомы, как таинственный пропуск элементов, их двойная обработка или другие странности.

Answer 3

Меня немного беспокоит ваша функция iswhole():

def iswhole(x):
    if x%1 == 0:
        return True
    else:
        return False

(Кстати, это можно переписать просто как return (x%1 == 0) и пропустить фрагменты return True и return False.)

Числа с плавающей точкой - нечетные существа:

>>> 10.0%1
0.0
>>> (10.1 * 10)%1
0.0
>>> (10.01 * 100)%1
0.0
>>> (10.001 * 1000)%1
0.0
>>> (10.0001 * 10000)%1
0.0
>>> (10.00001 * 100000)%1
0.0
>>> (10.000001 * 1000000)%1
0.0
>>> (10.0000001 * 10000000)%1
0.0
>>> (10.00000001 * 100000000)%1
1.1920928955078125e-07

Для ввода, такого как 6, это, похоже, не является проблемой, но может стать проблемой.для больших входов. Сравнение чисел с плавающей запятой проблематично .

Для проблемы 6 я хотел бы предложить, чтобы вместо изменяемого списка для отслеживания ваших данных вы могли бы использовать массив вместо.Массив никогда не нужно сортировать (тот факт, что в вашей программе есть sort(), пахнет как попытка исправить какую-то ошибку) и удаление элементов из середин списков часто чрезвычайнодорого.(Это sort в значительной степени означает, что ваша производительность все равно будет плохой. Не так уж и много для небольших входов, но попробуйте 1000000 в качестве отправной точки.) Установка элементов в массиве на 1 или 0 почти всегдагораздо дешевле, чем изменяемые списки.