 # Find the prime factor efficiently.

How to Find the prime factor efficiently?

1 Like

Use Sieve of Eratosthenes to save all prime numbers in primes[i], then use this functions:

``````vector < int > factors;
void pfac(int n){
for(int i=2;i*i<=n;i++)
if(prime[i]==1 && n%i==0)
factors.push_back(i);
}

bool prime[MAX]={true};
void seive(){
for(int i=2;i*i<MAX;i++){
if(prime[i]){
for(int j=2*i;j<MAX;j+=i){
prime[j]=0;
}
}
}
}``````
3 Likes

First use optimized sieve like this :-

``````int prime[MAXN+1] = {false};
void init(){
prime = 1;
for(int i = 2; i <= MAXN; i++){
if(!prime[i]){
prime[i] = i;
for(int j = i*i; j <= MAXN; j+=i)
prime[j] = i;
}
}
}
``````

Now for any number N, you can store its distinct prime factors like this:-

``````   vector<int> PFS;
cin>>num;
while(num > 1){
PFS.push_back(prime[num]);
int p = prime[num];
while(num % p == 0)
num /= p;
}
``````

here PFS is a vector that stores the prime factors of the given number
i.e if num is taken input as 6 then PFS will store 2 and 3.
the above method is quite fast and can calculate factorization uptill 1e7 within 1 sec on codechef servers. For bigger numbers you will definitely need much better algorithms

1 Like

http://codeforces.com/blog/entry/7262
This blog shares an approach to find the smallest prime numbers of all numbers in using sieve.
Then we can repeatedly divide the number from its least prime,then quotient from its least prime and so on. The complexity of doing this will be O(logn).

After using that modified sieve approach to find the least prime, we can do this.

vector factorize(int k)
{

``````    vector <int> ans;

while(k>1)
{
int sml=smallestp[k];
ans.push_back(sml);
while(k%sml==0)
k/=sml;
}
return ans;
``````

}

1 Like

The fastest approach I know is to do a sieve in O(n) saving the lowest prime factor. [e-maxx]
1

``````const int N = 10000000;
int lp[N+1];
vector<int> pr;

for (int i=2; i<=N; ++i) {
if (lp[i] == 0) {
lp[i] = i;
pr.push_back (i);
}
for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
lp[i * pr[j]] = pr[j];
}
``````

[although it’s not blazingly faster than the normal sieve] and do factorization in O(log(N)) as already mentioned by anurag_s2.

1 Like

use optimised sieve to store least prime factor of all the numbers upto 1e7 and find the prime factorisation of
using it .
Here’s my code :- http://ideone.com/zakE8Q

1 Like

I don’t understand about that, any one to clarify for me?

the exponent of prime p in n! is ∑∞i=1⌊npi⌋.

This can be computed in a finite number of steps because we can stop once pi becomes larger than n, so it takes O(logpn)=O(logn) steps to get the exponent of a single prime.

The number of primes up to n is approximately n/ln(n), so computing the factorization takes O(logn⋅n/logn)=O(n) steps. BY logmein123

That’s exceptionally confusing, which one is the suitable solution actually?

please give the Sieve of Eratosthenes function too.

1 Like

bool prime[MAX]={true};
void seive(){
for(int i=2;ii<MAX;i++){
if(prime[i]){
for(int j=2
i;j<MAX;j+=i){
prime[i]=0;
}
}
}
}

Tnq @neilit1992.

1 Like

What’s wrong with u? I try to solve to spoj problem. But u flagged me. This is not fair. Click this link : http://www.spoj.com/status/rashedcs/
And saw my all submission. You can not blame anyone with false statement. I think you understand.