Prime Factorization(Using Prime Sieve)

Prime factorisation of a number is finding all the prime factors of a number.
For example, prime factorisation of 120 can be written as:
120=2*2*2*3*5

One method for finding prime factorisation of a number is to check for each prime number(less than given number) whether it divides the given number or not. However,we can find prime factorisation of a number using Sieve of Eratosthenesin a much more efficient way. Before reading this post,please read the post about Sieve of Eratosthenes

We still use the array mark[]. However,mark[i] stores the smallest prime factor for a number i if i is non prime and i if i is prime(if number is prime,the number itself is its only prime factor).Since we mark multiples of primes only, starting from the smallest one,we store the smallest prime factor when any number is marked for the first time.The code for prime sieve can be updated to accommodate this change as follows:

void factorisation(int n)
{
    int mark[100000]={0},i,j;/*Initialise mark array with 0*/
    /*Mark all the multiples of 2 and 2 will be smallest prime factor for even numbers*/
    for(i=2;i<=n;i+=2)
        mark[i]=2;

    /*mark multiples of odd numbers between 3 and sqrt(n)*/
    for(i=3;i*i<=n;i+=2)
    {
        if(mark[i]==0)
        {
            for(j=i*i;j<=n;j+=2*i)
            {
            /*If number is being marked for the first time, i is its smallest prime factor*/
                if(mark[j]==0)
                    mark[j]=i;
            }
            mark[i]=i; /*For a prime number,number itself is the prime factor.*/
        }
    }
    /*for all prime numbers, store the number itself as its prime factor*/
    for(;i<=n;i+=2)
    {
        if(mark[i]==0)
            mark[i]=i;
    }
}

After storing prime factors,if we want to print prime factorisation of a number n,this can be done easily as follows:

void printfactors(int n)
{   
    /*keep on printing prime factors and keep dividing n by prime factor until n>1*/
    while(n>1)
    {
        printf("%d\t",mark[n]); 
// We divide the number by mark[n] because on dividing, we get the number equal to the product of the remaining prime factors   
        n=n/mark[n];
    }
} 

This content has been helpful to you?

Thanks for contributing!

Yes No