Crashing prime number calculator

[Caffiend]

Well, I've been picking at learning python, got tired of reading, and figured I'd try to replicate my prime number generator I wrote (with much TSDN forum help) in C++. I've hit a stumbling block... the program is supposed to print onscreen all the prime numbers between two numbers given to it, so if I put in 1 and 10, it should print out 1, 3, 5, 7 (I know, technically 1 isn't considered prime, and 2 should be on there, but otherwise...) Which it does, but then IDLE freezes and needs to be killed with system monitor (in ubuntu 6.06)... If it helps, I am using Python v. 2.4.3

And the code:

print
print
print "This program identifies all the prime numbers"
print "between two given numbers"
print

# I just wanted the start function to take two integers
# and pass them to prime_test, with num1 as testnum and
# num2 as maxnum.
def start():
    num1 = input("Please enter the lower number: ")
    num2 = input("Please enter the higher number: ")
    if num1 > num2:
        print "Please input the lower number first."
        start()
    elif num1 == num2:
        print "Please use 2 different numbers."
        start()
    elif (num1 < 0) or (num2 < 0):
        print "Please use positive integers only please."
        start()
    prime_test(num1, num2)


# I'm not sure where the problem is, but I think it
# is in this function.  testnum starts off as the lowest
# number to test, passed from num1 in the start function
# and increases until it reaches the maximum number of 
# maxnum, passed from num2 in the start function. 

def prime_test(testnum, maxnum):
    import math
    count = 3
    prime = True
    while testnum <= maxnum:
        if testnum % 2 == 0:
            testnum = testnum + 1
        elif testnum % 2 != 0:
            while count <= math.sqrt(testnum):
                if testnum % count == 0:
                    prime = False
                else:
                    count = count + 2
            if prime == True:
                print testnum
                testnum = testnum +1

start()

print "Do you want to start again?"
print "Type X and hit enter to exit,"
endprompt = raw_input("type anything else and press enter to start again: ")
if endprompt == 'x' or 'X':
    print
    print
    print "Goodbye!"
else:
    start()

Thanks for all the help so far!

[Loismustdie129]

I worked on it for a while and I found that I didn't get an error. I did have to shift the last IF function over to the place of the ELIF function in prime_test. Or:

def prime_test(testnum, maxnum):
    import math
    count = 3
    prime = True
    while testnum <= maxnum:
        if testnum % 2 == 0:
            testnum = testnum + 1
        elif testnum % 2 != 0:
            while count <= math.sqrt(testnum):
                if testnum % count == 0:
                    prime = False
                else:
                    count = count + 2
        if prime == True:
              print testnum
              testnum = testnum +1

I hope this helps.

[bartonc]

Here is the link to my original post regarding this.

[Caffiend]

Thanks Barton, i've seen that one before, and it's definitely a lot more efficient than the way I am going about it. Specifically though, I'm trying to calculate all the primes between two given numbers, mainly so that I can skip directly to the higher numbers, such as 10 ** 9. Also, for learning purposes, I can't quite figure out what is wrong with the code... Loismustdie fixed the problem with it crashing, however it now just prints out every odd number, both prime and non-prime... Does anyone know the mystery, or point me in the right direction?

[bvdet]

Thanks Barton, i've seen that one before, and it's definitely a lot more efficient than the way I am going about it. Specifically though, I'm trying to calculate all the primes between two given numbers, mainly so that I can skip directly to the higher numbers, such as 10 ** 9. Also, for learning purposes, I can't quite figure out what is wrong with the code... Loismustdie fixed the problem with it crashing, however it now just prints out every odd number, both prime and non-prime... Does anyone know the mystery, or point me in the right direction?

Here's a couple of functions for prime numbers - small and large:

def primes(low, high):
    lstA = range(2, high)
    lstB = []
    while len(lstA) > 0:
        n = lstA[0]
        if n >= low:
            lstB.append(n)
        cnt = 1
        while n*cnt < high:
            n1 = n*cnt
            if n1 in lstA:
                lstA.remove(n1)
            cnt += 1
    return lstB

# print ', '.join(map(str, primes(2, 200)))

import math
def large_primes(low, high):
    if high <= low:
        raise ValueError, 'Argument #2 must be greater than argument #1'
    elif (high-low) > 1000:
        raise ValueError, 'The difference between argument #2 and argument #1 must be less than 1001'
    pList = primes(2,200)
    numList = range(low, high)
    lpList = range(low, high)
    for num in numList:
        for p in pList:
            if num % p == 0:
                lpList.remove(num)
                break
    numList = lpList
    for num in numList:
        for i in [-1, 0, 1, 2, 3, 4]:
            k = 1
            while (6*k+i) < math.sqrt(num):
                if num % (6*k+i) == 0:
                    try:                   # There is a bug here, therefore the try
                        lpList.remove(num)
                        break
                    except:
                        pass
                k += 1
    return lpList

print ', '.join(map(str, large_primes(200000000000, 200000000100)))
'''
>>> 200000000023, 200000000033, 200000000041, 200000000051, 200000000069, 200000000077, 200000000093
'''

The function large_primes() ignores prime numbers less than 200 and limits the range to 1000. It works reasonably fast for 11 digits and fewer, depending on the range. I was getting this error at the noted try statement:

File "C:\SDS2_7.0\ma cro\Work In Progress\prime_ number.py", line 130, in large_primes
if num % (6*k+i) == 0:
ValueError: list.remove(x): x not in list

If someone can figure out why I would appreciate it.
HTH, BV :)

[ghostdog74]

Here's a couple of functions for prime numbers - small and large:

def primes(low, high):
    lstA = range(2, high)
    lstB = []
    while len(lstA) > 0:
        n = lstA[0]
        if n >= low:
            lstB.append(n)
        cnt = 1
        while n*cnt < high:
            n1 = n*cnt
            if n1 in lstA:
                lstA.remove(n1)
            cnt += 1
    return lstB

# print ', '.join(map(str, primes(2, 200)))

import math
def large_primes(low, high):
    if high <= low:
        raise ValueError, 'Argument #2 must be greater than argument #1'
    elif (high-low) > 1000:
        raise ValueError, 'The difference between argument #2 and argument #1 must be less than 1001'
    pList = primes(2,200)
    numList = range(low, high)
    lpList = range(low, high)
    for num in numList:
        for p in pList:
            if num % p == 0:
                lpList.remove(num)
                break
    numList = lpList
    for num in numList:
        for i in [-1, 0, 1, 2, 3, 4]:
            k = 1
            while (6*k+i) < math.sqrt(num):
                if num % (6*k+i) == 0:
                    try:                   # There is a bug here, therefore the try
                        lpList.remove(num)
                        break
                    except:
                        pass
                k += 1
    return lpList

print ', '.join(map(str, large_primes(200000000000, 200000000100)))
'''
>>> 200000000023, 200000000033, 200000000041, 200000000051, 200000000069, 200000000077, 200000000093
'''

The function large_primes() ignores prime numbers less than 200 and limits the range to 1000. It works reasonably fast for 11 digits and fewer, depending on the range. I was getting this error at the noted try statement:

File "C:\SDS2_7.0\ma cro\Work In Progress\prime_ number.py", line 130, in large_primes
if num % (6*k+i) == 0:
ValueError: list.remove(x): x not in list

If someone can figure out why I would appreciate it.
HTH, BV :)

did not rreally run your entire script, but you can try

...
numList = lpList[:]
...

[bvdet]

did not rreally run your entire script, but you can try

...
numList = lpList[:]
...

Thanks, but it did not help. It bombs on this number: 2000000159

[bvdet]

The code for large_primes() that I posted earlier was incorrect. The following seems to work correctly:

def large_primes(low, high):
    if high <= low:
        raise ValueError, 'Argument #2 must be greater than argument #1'
    elif (high-low) > 30000:
        raise ValueError, 'The difference between argument #2 and argument #1 must be less than 1001'
    pList = primes(2,200)
    numList = range(low, high)
    lpList = range(low, high)
    for num in numList:
        for p in pList:
            if num % p == 0:
                lpList.remove(num)
                break
    numList = lpList[:]
    for num in numList:
        for i in xrange(9, int(math.ceil(math.sqrt(high))), 2):
            if num % i == 0:
                lpList.remove(num)
                break
    return lpList

pList = large_primes(20000000000, 20000001000)

>>> 20000000089, 20000000113, 20000000117, 20000000179, 20000000201, ..........