How to Find the prime factor efficiently?

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;
}
}
}
}
```

First use optimized sieve like this :-

```
int prime[MAXN+1] = {false};
void init(){
prime[1] = 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

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;
```

}

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.

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

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.

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[i]=0;

}

}

}

}

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.

Do you open the website mistakenly?