Prime Numbers

[electric916]

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)

[bvdet]

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)

That is a good start. To compile a list of factors, you can create a function similar to isprime(). Create an empty list. You will need to set the range upper limit to (n/2)+1. If n % x returns 0, append n to the list. The function should return the list.

[electric916]

Having trouble still with listing the factors if it is not a prime number. Any advice would be great. Here's what I got.

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
 
 
 
 
if isprime(n) is True:
               print n, "is a prime number!"
if isprime(n) is False:
                print n, "is not a prime number" 
print isprime(n)

[Laharl]

Python's true and false values are 'True' and 'False', which are case-sensitive. Thus, regardless of your isprime code, you'll get errors there.

[bvdet]

Having trouble still with listing the factors if it is not a prime number. Any advice would be great. Here's what I got.

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
 
 
 
 
if isprime(n) is True:
               print n, "is a prime number!"
if isprime(n) is False:
                print n, "is not a prime number" 
print isprime(n)

The code is correct, but you seem to have an indentation problem. There is no need to check if the value returned by the function is True or False.

if isprime(n):
    print n, "is a prime number!"
else:
    print n, "is not a prime number" 
print isprime(n)

[electric916]

Ok. Getting close to the end. 2 questions.
1. Still have problem listing factors if number is not prime, in part 1 of assignment.
2. How do I output p to a string so I can output p to a file? It is towards end of code.
3. Which code do i use to exit the program if the user enters 0?
Here is what I got.

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
if isprime(n):
    print n, "is a prime number!"
else:
    print n, "is not a prime number"
 
 
 
 
 
 
 
 
 
 
 
 
 
n = input ("Please enter a number greater than 2: ")
outfile = 'primes-'+str(n)+'.txt'
output = open (outfile, "w")
def get_factors(n):
    List1 = []
    List2 = []
    List3 = []
    for x in range(2, int(n**0.5)+1):
        if n % x == 0:
            List1 = List1 + [x]
            for y in List1:
                c = n / y
                if c not in List2:  
                    List2 = List2 + [c]
    List3 = List1 + List2
    List3.sort()
    return List3
def prime_number(n):
    List4 = []
    for n in range(2, n+1):
        if get_factors(n) == []:
            List4 = List4 + [n]
    return List4
 
p = prime_number(n)
output.write(p)
print "Found", len(prime_number(n)), "numbers; please check file primes-",n,".txt"
 

[bvdet]

Ok. Getting close to the end. 2 questions.
1. Still have problem listing factors if number is not prime, in part 1 of assignment.
2. How do I output p to a string so I can output p to a file? It is towards end of code.
3. Which code do i use to exit the program if the user enters 0?
Here is what I got.

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
if isprime(n):
    print n, "is a prime number!"
else:
    print n, "is not a prime number"
 
 
 
 
 
 
 
 
 
 
 
 
 
n = input ("Please enter a number greater than 2: ")
outfile = 'primes-'+str(n)+'.txt'
output = open (outfile, "w")
def get_factors(n):
    List1 = []
    List2 = []
    List3 = []
    for x in range(2, int(n**0.5)+1):
        if n % x == 0:
            List1 = List1 + [x]
            for y in List1:
                c = n / y
                if c not in List2:  
                    List2 = List2 + [c]
    List3 = List1 + List2
    List3.sort()
    return List3
def prime_number(n):
    List4 = []
    for n in range(2, n+1):
        if get_factors(n) == []:
            List4 = List4 + [n]
    return List4
 
p = prime_number(n)
output.write(p)
print "Found", len(prime_number(n)), "numbers; please check file primes-",n,".txt"
 

There is a simpler way to get a list of factors. You don't need function prime_number. Iterate on range(2, (number/2)+1).

>>> factorlist = [i for i in range(2, int(297/2.0)+1) if not 297%i]
>>> factorlist
[3, 9, 11, 27, 33, 99]
>>> factorlist = [i for i in range(2, int(97/2.0)+1) if not 97%i]
>>> factorlist
[]
>>> 

Skip the function call if the number is 0 with an if statement.

>>> n = 0
>>> if n > 1:
...     print "Proceed"
... else:
...     print "Exit"
...     
Exit
>>> 

HTH

[electric916]

I appreciate your help so much. I swear these are my last questions. I am almost completely done. I just have 2 problems.
1. I still cant get the program to stay in the first part UNLESS the user inputs 0, then it should move on to the second part of the program.
2. Still having problems writing results of part 2 of assignment to a file. I think i need to make results into a string then write to a file.

[bvdet]

I appreciate your help so much. I swear these are my last questions. I am almost completely done. I just have 2 problems.
1. I still cant get the program to stay in the first part UNLESS the user inputs 0, then it should move on to the second part of the program.
2. Still having problems writing results of part 2 of assignment to a file. I think i need to make results into a string then write to a file.

Try something like this:

def part_one():
    while True:
        num = int(raw_input("Enter a positive number or 0 to exit."))
        if num > 0:
            ....call your prime number function here....
        else:
            print 'Exiting part one'
            return
 
def part_two():
    print 'This is part two.'
 
if __name__ == '__main__':
    part_one()
    part_two()

Here is some sample code showing how to write a list of numbers to a file:

# write a list of numbers to file
# open a file, creating a file object
listofnums = [1,2,3,4,5,6,7,8]
f = open(file_name, 'w')
# convert the number list to a string
numstr = ','.join([str(num) for num in listofnums])
# add newline characters as required
f.write('This is a list of numbers.\n')
f.write('%s\n' % numstr)
# close file object, flush data to disc
f.close()

[docdiesel]

Hi,

I'm not a Phyton programmer, but may give you another little hint. If calculating up to "number/2" or "(number/2)+1", your program is wasting time. You've just got to check up to the next upper int of the square root.

Next, try to keep them all integers, because most cpus calculate them faster than floats:

start = 2;
stop  = int (sqrt( number ) + 1 );
 
i = start;
while( i^2 <= stop )
{
  check_if_is_prim(number);
  i++;
}

Regards,

Bernd

[bvdet]

Hi,

I'm not a Phyton programmer, but may give you another little hint. If calculating up to "number/2" or "(number/2)+1", your program is wasting time. You've just got to check up to the next upper int of the square root.

Next, try to keep them all integers, because most cpus calculate them faster than floats:

start = 2;
stop  = int (sqrt( number ) + 1 );
 
i = start;
while( i^2 <= stop )
{
  check_if_is_prim(number);
  i++;
}

Regards,

Bernd

Bernd,

Part of the OP's problem is to compile a list of the factors for a given number. To do that, you must go to some point beyond int(sqrt(number))+1. As you pointed out, it is wasting CPU time. Alternatively, you can determine the factors as you suggested and finish out the list with integer division.

def factors(num):
    outList = [i for i in xrange(2, int(num**0.5)+1) if not num%i]
    outList.extend([num/outList[i] for i in range(len(outList)-1, -1, -1)])
    return outList

Sample:

>>> factors(1663868945)
[5, 607, 3035, 548227, 2741135, 332773789]
>>> factors(17546598733)
[4259, 4119887L]
>>> 

Other optimizations could be done, but this works fairly well for numbers with less than 14 digits. Thanks for pointing this out. The code I suggested code was a bit too simplistic.

[docdiesel]

Part of the OP's problem is to compile a list of the factors for a given number.

Uh, I missed that part. I must have been too low on coffee. Furthermore, now I see there're two * in your range condition part "int(n**0.5)+1". I guess that means square root in Python??

Regards,

Bernd (@ home in perl, php and many others, but not in python)

[bvdet]

Furthermore, now I see there're two * in your range condition part "int(n**0.5)+1". I guess that means square root in Python??

Regards,

Bernd (@ home in perl, php and many others, but not in python)

Yes Bernd. That avoids importing math to access sqrt().