For loop repeating/stuck? Python 3.2

Question

I am trying to write a python script for Sieve of Eratosthenes. I have everything done, but when I tell the program to test each number if it is a multiple of at least one of the prime numbers below the √input. It goes well but when I try to remove a multiple it works until it tries to delete 6 twice... I've been looking over my code and can't seem to find out why. I'm rather new to Python so help would be much appreciated! --- Note my code's spacing is off due to SOF's way of making code blocks:

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

Your code can be much simplified by the following realisations:

• The numbers up to a number n can easily be generated as needed, they don't have to be calculated berforehand and stored in a list.

• 2 is the only even prime, so you only need to test odd numbers.

• All numbers can be fully factorised into prime factors, uniquely (this is called the fundamental theorem of arithmetic). This means that the only numbers which you need to try dividing by are the primes you have previously calculated --- all other numbers will be divisible by at least one of those primes anyway (or they would be primes themselves).

Try something along these lines:

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

Also, please pay attention to spacing and indentation. In Python, when you get your spacing wrong it is not only difficult to read, but a runtime error.

Answer 2

I'm a little worried about your iswhole() function:

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

(Incidentally, this could be re-written as simply return (x%1 == 0) and skip the return True and return False pieces.)

Floating point numbers are odd creatures:

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

For an input such as 6, this doesn't seem likely to be the problem, but it might become a problem for larger inputs. Comparing floating point numbers is troublesome.

For the 6 problem, I'd like to suggest that instead of a mutable list to keep track of your data, you might wish to use an array instead. The array never needs to be sorted (the fact that you have a sort() in your program smells a bit like trying to paper over some kind of bug) and deleting elements from the middles of lists is often extremely expensive. (That sort pretty much means your performance is going to be poor anyhow. Not a big deal for small inputs, but try 1000000 as a starting point.) Setting elements in an array to 1 or 0 is almost always far cheaper than mutable lists.

Answer 3

I see a problem with this bit:

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

You call thelist.remove(x) and thelist.sort() while iterating over thelist. You generally don't want to modify a structure you're iterating over in Python. It usually confuses the internal machinery doing the iteration; you get symptoms like mysteriously skipping elements or processing them twice, or other weirdness.