Hey guys, 
Hope you all are doing great. I am back with another problem of Project Euler on


Project Euler #3: Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of a given number N?
Input Format
First line contains T, the number of test cases. This is followed by T lines each containing an integer N.
Output Format
For each test case, display the largest prime factor of N.
Constraints
1T10
10N1012
Sample Input
2
10
17
Sample Output
5
17

Algorithm:


For finding prime numbers we need to check whether a number is not divisible by any number except 1 and itself.

So as a brute force it is to iterate through all numbers less than it and check of the divisibility.

But as we search for prime numbers < N, its time complexity will be
O(N^2)


Hence for large value brute force algorithm will fail.

So we can find a pattern to decrease the number of iterations:

As the first 5 prime numbers are 2, 3, 5, 7 and 11.
We can filter the multiples of these, so number of iteration will become less than half

Further,

If a number n is not a prime, it can be factored into two factors a and b:
n = a*b
If both a and b were greater than the square root of n a*b would be greater than n. So at least one of those factors must be less or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.
So in worst case the time complexity will be
O(n*log(n))
And Presto!! We are Done!!

Now to program this in python, you need to take care of all conditions and make it work. Here is a snippet for my submission to the problem

Program:


import math
def is_prime(num): # Here you can add condition for exclusion of multiples of 2,3,5,7 & 11
 for j in range(2,int(math.sqrt(num)+1)):
  if (num % j) == 0: 
   return False
 return True
t=input()
while(t>0):
    t=t-1;
    n=input()
    for i in range(n,2,-1):
        if(n%i==0 and is_prime(i)):
            print i
            break;
0

Add a comment

Popular Posts
Popular Posts
print ("About Me")
print ("About Me")
My Photo
HYDERABAD, Telangana, India
Blog.History(All)
Labels
Total Pageviews
Total Pageviews
21466
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.