Question

Code in Python:

We have seen in class that the method of trial division can be used to find the smallest prime factor of an integer n ≥ 2. For this problem, we want to use trial division to find the largest prime factor of n instead.

Task: Write a procedure in Python that takes an integer n ≥ 2 as input, and returns its largest prime factor.

Test Values: The largest prime factor of 13195 is 29. The largest prime factor of 23508701 is 322037.

Answer 1

#Python program to find the largest prime factor of a given number

def largestPrime(number):
#This function accepts a number and return the largest prime factor
factor=2;
j=2;
while (number>1) :
while (number % j==0):
factor=j; # assigning/overwriting the larger prime factor to factor
number=number/j;
j=j+1; # if j does not equally devides number
return factor
  
  
k1=largestPrime(13195);
print k1
k2=largestPrime(23508701);
print k2

#-----------------------------------------------------

snapshot

output

largestprime.py - C:/Python27/largestprime.py (2.712) File Edit Format Run Options Window Help #Python program to find the largest prime factor of a given number def largestPrime (number) #This function accepts a number and return the largest prime factor factor-2 5-2: while (number>1) while (number % j--0): factor-j; # assigning/overwriting number=number/j ; the larger prime factor to factor j=j +1 ; return factor # if j does not equally devides number kl-largestPrime (13195) print kl k2-largestPrime (23508701) print k2 Ln: 5 Col: 13

CWindows system32\cmd.exe C:NPython27>python largestprime.py 29 322037 C: \Python27>