User:Kithira/Course Pages/CSCI 12/Assignment 2/Group 1/Homework 2

Finding Prime Factors Using Python

Here is a program written in Python (programming language) that allows the user to input any positive integer and receive a list of the prime factors:

from Factors import Factor
from PrimeNumber import Prime 

def PrimeFactor(N): 
   M = [] 
   for L in Factor(N): 
       if Prime(L): 
           M.append(L) 
   return M 

def _test():
   assert( PrimeFactor(6) == [2,3] ) 
   print "Enter a number greater than 1 to find its prime factors: " 
   T = int( raw_input() ) 
   print "The prime factors of", T, "are:", PrimeFactor(T) 

if __name__ == '__main__': 
   _test()

Using Factor( ), the program goes through each factor of the designated number and checks if it is prime, using Prime( ). If True, the factor is added to the M list, then once all digits have been checked it returns the final list. Before allowing the user to input a number, it tests an input of 6 automatically to ensure any changes have not affected its functionality.

The code above relies upon the usage of existing programs to (1) find the factors and (2) check if a number is prime, which the user can provide themselves (if they have already written their own). To do this simply change the from location and the import module. Below are a couple examples of possible programs:

Factors

Returns a list of all the factors of a number.

def Factor(X):
    result = []
    n = 1
    while n <= X:
        if (X/n)*n == X:
            result.append(n)
            n += 1
        else:
            n += 1
    return result

Prime

Returns a boolean (True/False) of whether a number is prime.

from Factors import Factor

def Prime(X):
    return bool( len( Factor(X) ) == 2 )

This code relies upon the structure of the Factors program above, using the fact that the factors of a prime number are always 1 and itself.