Calculate all possible factors of a prime

问题:

Was going through a Python Tutorial and came across an example to check whether a number is prime or not. I changed a few things so that the result would display a list of all possible factors of the number, if the number is not a prime, However, the code didn't work.

Code:

def isprime(number):
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, number):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
            continue
        if notprime == 1:     
            return number, "is not a prime because of these factors", fnum  
        else:
            return True
num =int(raw_input("Enter number: "))
print isprime(num)

Output:

Enter number: 12
Reticulating Splines...
(12, 'is not a prime because of these factors', [1, 2, 3, 4])
>>> 
Enter number: 25
Reticulating Splines...
(25, 'is a prime number')

Expected Output:

Enter number: 12
Reticulating Splines...
(12, 'is not a prime because of these factors', [1, 2, 3, 4, 6])

Enter number: 25
Reticulating Splines...
(25, 'is not a prime because of these factors', [1,5])

Poor control structure is my guess, but can someone fix my code?

I understand how range() works: In this case range() is given a start and a stop value, step defaults to 1. I understand that continue, continues a loop, but can I use it with if? I think that is wrong.

UPDATE
Solved, problem with indentation the continue should have been for the for loop, ditto for the if...notprime.

def isprime(number):
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, number):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
    if notprime == 1:     
        return number, "is not a prime because of these factors", fnum  
    else:
        return number, "is a prime number"
num =int(raw_input("Enter number: "))
print isprime(num)

Update2: (Thx to @neil)
And the continue is plain stupid

Updated Code and speed comparisons between n/2 and sqrt(n) Thanks to @neil and @emmanuel
n/2 code: v2

import time
def isprime(number):
    start=time.clock()
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, (number/2)+1):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
    end=time.clock()
    if notprime == 1:     
        return number, "is not a prime because of these factors", fnum, "Time taken", end-start  
    else:
        return number, "is a prime number. Time Taken", end-start
print "Prime or factor calculator v2 using n/2"
print #
num =int(raw_input("Enter number: "))
print isprime(num)

sqrt(n) code: v3

import math, time
def isprime(number):
    start=time.clock()
    print "Reticulating Splines..."
    fnum = [1,]
    last = int(math.ceil(math.sqrt(number)))
    for p in range(2, last + 1):
        if (number % p) == 0:
            fnum.append(p)
            fnum.append(number / p)
    # Remove duplicates, sort list
    fnum = list(set(fnum))
    fnum.sort()
    end=time.clock()
    if len(fnum) > 1:     
        return number, "is not a prime because of these factors", fnum ,"Time taken", end-start 
    else:
        return True, "Time taken", end-start

print "Prime or factor calculator v3 using sqrt(n)"
print #

num =int(raw_input("Enter number: "))

print isprime(num)

Output(Showing only time)

Time for sqrt(n) code: v3
Prime or factor calculator v3 using sqrt(n)
Enter number: 999999
Time taken', 0.0022617399697466567

Time for n/2 code: v2
Prime or factor calculator v2 using n/2
Enter number: 999999
Time taken: 0.11294955085074321

Time for original code(n): v1
Prime or factor calculator v1
Enter number: 999999
Time taken: 0.22059172324972565

v1 and v2 could not handle numbers 999999999, 999999999999 and 999999999999999, both gave a MemoryError

However v3 handled the three numbers:
999999999 : 0.010536255306192288
999999999999 : 0.75631930873896636
999999999999999 : 24.04511104064909

The shell hangs for 9999999999999999 and gives a MemoryError for 999999999999999999

Thanks to @Lennart, I am thinking of rewriting the code in a more OOP friendly way, by using classes. But I don't seem to be doing it right.

回答1:

The problem is your indentation - if notprime==1: shouldn't be within the for loop. It should only have one level of indentation.

Also, the continue is unnecessary.

EDIT:

An improvement you can make (I was just working on primes last night for a Project Euler problem) is to only loop to n/2 - there can't be a factor greater than half the number.

回答2:

Your final if notprime ... and the three lines following it are indented too far and as such is executed inside the loop, instead of outside.

回答3:

You return after testing only one number. Move the if tests and the returns to outside of the for loop.

Also, returning True if it is a prime, and a string if it is not is unpractical. If you then call

if isprime(7):

That will always evaluate as True. I've improved things a bit:

def factors(number):
    fnum=[]
    for p in range(2, number):
        if (number % p) == 0:
            fnum.append(p)
    return fnum

for x in range(100):
    f = factors(x)
    if f:
        print x, "is not a prime and has factors", f
    else:
        print x, "is a prime"

回答4:

@neil:

"An improvement you can make ... is to only loop to n/2 - there can't be a factor greater than half the number."

By the way, the highest value you need to test is int(math.ceil(math.sqrt(n))), no need to go to n/2 if each time you get a value, you get the associated one (i.e. if a x b = n, either a or b is lower than the square root of n and the other one is greater):

def isprime(number):
    print "Reticulating Splines..."
    fnum = [1,]
    last = int(math.ceil(math.sqrt(number)))
    for p in range(2, last + 1):
        if (number % p) == 0:
            fnum.append(p)
            fnum.append(number / p)
    # Remove duplicates, sort list
    fnum = list(set(fnum))
    fnum.sort()
    if len(fnum) > 1:     
        return number, "is not a prime because of these factors", fnum  
    else:
        return True

Greater performance, even if at the end the list is not sorted (but this can be done inside the loop by adding the 2 numbers p and number / p at the good indexes).