is there any tutorial for finding prime factors of a large number…?? plzz help.
1 Like
Given a number n, write an efficient function to print all prime factors of n. For example, if the input number is 12, then output should be “2 2 3″. And if the input number is 315, then output should be “3 3 5 7″.
Following are the steps to find all prime factors.
- While n is divisible by 2, print 2 and divide n by 2.
- After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.
- If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.
include<stdio.h>
include <math.h>
// A function to print all prime factors of a given number n
void primeFactors(int n)
{
// Print the number of 2s that divide n
while (n%2 == 0)
{
printf("%d ", 2);
n = n/2;
}
// n must be odd at this point. So we can skip one element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i = i+2)
{
// While i divides n, print i and divide n
while (n%i == 0)
{
printf("%d ", i);
n = n/i;
}
}
// This condition is to handle the case whien n is a prime number
// greater than 2
if (n > 2)
printf ("%d ", n);
}
/* Driver program to test above function */
int main()
{
int n = 315;
primeFactors(n);
return 0;
}
How does this work?
The steps 1 and 2 take care of composite numbers and step 3 takes care of prime numbers. To prove that the complete algorithm works, we need to prove that steps 1 and 2 actually take care of composite numbers. This is clear that step 1 takes care of even numbers. And after step 1, all remaining prime factor must be odd (difference of two prime factors must be at least 2), this explains why i is incremented by 2.
Now the main part is, the loop runs till square root of n not till. To prove that this optimization works, let us consider the following property of composite numbers.
Every composite number has at least one prime factor less than or equal to square root of itself.
This property can be proved using counter statement. Let a and b be two factors of n such that a*b = n. If both are greater than [Tex]\sqrt{n}[/Tex], then a.b > [Tex]\sqrt{n} * \sqrt{n}[/Tex] which contradicts the expression “a * b = n”.
In step 2 of the above algorithm, we run a loop and do following in loop
a) Find the least prime factor i (must be less than [Tex]\sqrt{n}[/Tex])
b) Remove all occurrences i from n by repeatedly dividing n by i.
c) Repeat steps a and b for divided n and i = i + 2. The steps a and b are repeated till n becomes either 1 or a prime number.
1 Like
What you’re looking for is prime factorisation. There are many heuristic algorithms, most of them pretty complicated, and all of them well googlable.
And no, you probably won’t be able to factorise numbers up to 10^{18} before Monday.
9 Likes
Well, he might have a PhD in Mathematics and/or google searching and might be able to find some effcient way 
I did the same pain of asking the same question.After googling I find that it is not possible to solve that question by using this approach.Dude think of some other logic and trust me the other logic is much simple but yet tricky.Took me 3 days to find out
May someone provide a C/C++ implementation of Pollard Rho Integer Factorization algorithm.
how much large number is this?
please be specific in term of constraints…
give the range of number
if range is <10^16
use can get all factor at most one second using sqrt(N) time complexity method
method is simple
k=sqrt(N);
for(i=1;i<=k;i++){
if(N%i==0){
if(I!=N/i)cout<<i<<" "<<N/i<<endl;
else cout<<i<<endl;
}
}
but this method use sqrt(N) time complexity
Read Pollard rho integer factorisation. link is http://www.cs.colorado.edu/~srirams/classes/doku.php/pollard_rho_tutorial
1 Like
It can calculate the prime factorisation of numbers till 10^20 in about no time. You can also try the problems FACT1 and FACT0 on Spoj to check the same.
will this algorithm always works…?? i am asking this bcoz it uses random numbers.!
You Can use Brent Algorithm which uses tricky Way to detect cycle and it uses core concept of pollard rho but more effecient than pollard rho…google it you will know …
1 Like
I’m assuming you are asking for SIMPLSUM problem. Basically you need Prime factorization. Just go through this BLOG. It’ll help you to solve the problem.
1 Like