[thispc]

a Modification to classic sieve of eratosthenes

Code: (Select All)

#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: (Select All)

void printfact(int n,int small[])
{
while(n>1)
{
cout<<small[n]<<" ";
n=n/small[n];
}
cout<<"\n";
}

Time::log n