+- Post4VPS Forum | Free VPS Provider (https://post4vps.com)
+-- Forum: Geek World (https://post4vps.com/Forum-Geek-World)
+--- Forum: Scripting & Programming (https://post4vps.com/Forum-Scripting-Programming)
+--- Thread: Fastest way to prime factorize a number!! (/Thread-Fastest-way-to-prime-factorize-a-number)
Fastest way to prime factorize a number!! - thispc - 07-30-2016
a Modification to classic sieve of eratosthenes
Code:
#include<bits/stdc++.h>
using namespace std;
void sieve(int n)
{
bool prime[n+1];
int small[n+1];
small[1]=1;
prime[1]=0;
memset(prime,1,sizeof(prime));
for(int i=2;i<=n;i++)
{
if(prime[i])
{
small[i]=i;
for(int j=i;i*j<=n;j++)
{
if(prime[j*i])
{
prime[j*i]=0;
small[j*i]=i;
}
}
}
}
for(int i=1;i<=n;i++)
cout<<small[i]<<" ";
cout<<"\n";
}
int main(void)
{
int n=20;
sieve(n);
}here small[i] array is smallest prime factor of given index i;
It can be used to print all prime factors as follows::
Code:
void printfact(int n,int small[])
{
while(n>1)
{
cout<<small[n]<<" ";
n=n/small[n];
}
cout<<"\n";
}Time::log n