Prime Numbers

[zclevenger]

I have a homework assignment i Am totally confused on. I started with a basic code to determine if a number is prime or not, but need guidance from here. I will post assignment details then what I have so far.

Problem 1: Is it a prime number?
Write a Python program that allows the user to enter a whole number greater than 1 and that determines whether or not this number is a prime number. If it is a prime number, then
this information is simply printed. If it is not a prime number, then the list of factors (or divisor) of that number is returned. Here is a sample session of the program:

Please enter a number greater than 1 (0 for exit): 13757
13757 is a prime number!

Please enter a number greater than 1 (0 for exit): 10281
10281 is not a prime number.
It has the factors [3, 23, 69, 149, 447, 3427]
Please enter a number greater than 1 (0 for exit): 0
Thanks and good bye!

Approach: Your main program has a loop that asks the user for a number, as shown above. It exits if the user enters the number 0. The number input by the user is used to call a user-defined function get factors. For a number n, this function determines all factors of n and returns these factors as a list, which is then output in the main program. If the returned list is empty, then this means that n is a prime number. So you have to take care of these two cases (empty versus non-empty list) in your main program. Thus, the main algorithm of your program is realized in the function get factors. There are several ways to determine whether or not a given number is a prime number. You have to find an efficient way to determine all non-trivial factors of a number n in the function get factors. For “smart” (i.e.,
time efficient) solutions, we will give extra points!

Problem 2: How many prime numbers are there? (8 Points)
Write a Python program that asks the user for a number n and then writes all prime numbers less than or equal to n into a file called primes-n.txt. That is, the number n is part of the filename. Here is a sample session:

Please enter a number greater than 2: 50
Found 15 prime numbers; please check file primes-50.txt
For this example, the file primes-50.txt contains one prime number per line, e.g.,
2
3
5
7
11
13
17
....
41
43
47

HERE IS WHAT I HAVE SO FAR. JUST STARTED.

n = input ("Please enter a number greater than 1 (0 for exit):")

def isprime(n):
    '''check if integer n is a prime'''
    # range starts with 2 and only needs to go up the squareroot of n
    for x in range(2, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

print isprime(n)

[jrcagle]

That's a good function. You did all of the sensible optimizations.

But now, notice that your design requirement is to print the factors of your number ...

so ... modify your function (same loop, different action at the if n % x == 0: branch) so that it generates a list of all of the factors of n.

Then isprime() would look like this:

def factors(n):
    ...
    (your cool factoring function goes here)

def isprime(n):
    if factors(n) == [1,n]:
       return True
    else:
       return False

Jeff

[BearofNH]

The only even number you need try is 2. So I suggest you replace for x in range(2, int(n**0.5)+1): with for x in [2]+range(3, int(n**0.5),2): Also remember a number may have multiple equal prime factors, e.g., 40 = 2*2*2*5.

[woooee]

The assignment says "For a number n, this function determines all factors of n and returns these factors as a list" so I would assume that the number 54 would return (2, 3, 6), and their other half (27, 18, 9) as a list, meaning the program would want to use all of the even numbers up to n**0.5. It would return an empty list of length zero if the number is a prime number.

[zclevenger]

Having some trouble with printing whether the number is prime or not, rather than printing true or false. I tried

if isprime(n) is true:
               print n ("is a prime number")

Definately not right. And also having trouble still with listing the factors if it is not a prime number. Any advice would be great.

[jrcagle]

Here's the correct Python:

print n, "is a prime number"

About writing the factors function:

do you know how to use lists? If not, check the Python docs for some examples.

wooee, I think the most straightforward interpretation is that the function returns the list of factors:

>>> factors(54)
[1,2,3,6,9,18,27,54]

Jeff

[Arob1000]

Here's the correct Python:
>>> factors(54)
[1,2,3,6,9,18,27,54]

Jeff

I am also doing this assignment...this thread has helped a bit and I'm a little farther than the OP, but I'm having trouble with the second part of the assignment. I can get all of the prime factors of a number, but it returns it as a list and I can't figure out how to write those numbers to a file. Also, how do I make the output file's name include the number that the user inputs? ie if the user imputs 50, "prime-50.txt" instead of "prime-num.txt"
Also, don't steal my code, cause I don't want to get sent to SJA...thanks
Here is my code:

def get_factors(num):
    L = []
    NewL = []
    FinalL = []
    rootnum = num**.5
    for i in range(2, int(rootnum)+1):
        if num % i == 0:
            L = L + [i]
            for x in L:
                c = num / x
                if c not in NewL:  
                    NewL = NewL + [c]
    FinalL = L + NewL
    FinalL.sort()
    return FinalL
def prime(num):
    L2 = []
    for i in range(2, num+1):
        if get_factors(i) == []:
            L2 = L2 + [i]
    return L2

num = input ("Please enter a number greater than 2: ")
outname = "primes-num.txt"
output = open (outname, "w")
p = prime(num)
print p
output.write (p)
print "Found", len(prime(num)), "numbers; please check file primes-",num,".txt"

[katharnakh]

outname = 'primes-' + str(num) + '.txt'   #Concantenating the input number('int' type), after converting it to string type

[Arob1000]

I am also doing this assignment...this thread has helped a bit and I'm a little farther than the OP, but I'm having trouble with the second part of the assignment. I can get all of the prime factors of a number, but it returns it as a list and I can't figure out how to write those numbers to a file. Also, how do I make the output file's name include the number that the user inputs? ie if the user imputs 50, "prime-50.txt" instead of "prime-num.txt"
Also, don't steal my code, cause I don't want to get sent to SJA...thanks
Here is my code:

def get_factors(num):
    L = []
    NewL = []
    FinalL = []
    rootnum = num**.5
    for i in range(2, int(rootnum)+1):
        if num % i == 0:
            L = L + [i]
            for x in L:
                c = num / x
                if c not in NewL:  
                    NewL = NewL + [c]
    FinalL = L + NewL
    FinalL.sort()
    return FinalL
def prime(num):
    L2 = []
    for i in range(2, num+1):
        if get_factors(i) == []:
            L2 = L2 + [i]
    return L2

num = input ("Please enter a number greater than 2: ")
outname = "primes-num.txt"
output = open (outname, "w")
p = prime(num)
print p
output.write (p)
print "Found", len(prime(num)), "numbers; please check file primes-",num,".txt"

I figured it out, thanks for the help guys!

[woooee]

I figured it out, thanks for the help guys!

I hope you will test the code you posted if that is your final version.

Here's the correct Python:
>>> factors(54)
[1,2,3,6,9,18,27,54]

The number one is not usually included as a factor since it is a factor of all numbers. The same is true for the number itself. The OPs for loop is
for x in range(2, int(n**0.5)+1):
as it should be. The loop starts at 2, which we want in order to eliminate the number one, and ends with n**0.5+1 which is all the farther you have to go, and that also eliminates the number itself. A prime number should return an empty list, since it has no factors.

[jrcagle]

Well, it probably depends on what the prof asks for.

1 is excluded from the list of *prime* factors for the reason you cite. And as you pointed out above, duplicate prime factors are included, so that any given number has a unique prime factorization.

But the list of factors of n always includes 1 and n. Hence the standard definition of a prime: "a number with exactly two factors."

Regards,
Jeff

[Arob1000]

I hope you will test the code you posted if that is your final version.The number one is not usually included as a factor since it is a factor of all numbers. The same is true for the number itself.

Yes I did test my code and that wasn't my final version, just the one I had at that time. Thanks for looking out though.