Hey guys,
Hope you all are doing great. I am back with another problem of Project Euler on
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 containsT , the number of test cases. This is followed by T lines each containing an integer N .
First line contains
Output Format
For each test case, display the largest prime factor ofN .
For each test case, display the largest prime factor of
Constraints
1≤T≤10
10≤N≤1012
Sample Input
2
10
17
Sample Output
5
17Algorithm:
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:
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,
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;
Add a comment