Print all prime factors and their powers

Given a number N, print all its unique prime factors and their powers in N.

Input: N = 100
Output: Factor Power
          2      2
          5      2

Input: N = 35
Output: Factor  Power
          5      1
          7      1

Simple Solution is to first find prime factors of N. Then for every prime factor, find the highest power of it that divides N and print it.

An Efficient Solution is to use Sieve of Eratosthenes.

1) First compute an array s[N+1] using Sieve of Eratosthenes.

s[i] = Smallest prime factor of "i" that
       divides "i".

For example let N  = 10
  s[2] = s[4] = s[6] = s[8] = s[10] = 2;
  s[3] = s[9] = 3;
  s[5] = 5;
  s[7] = 7;


2) Using the above computed array s[], we
   we can find all powers in O(Log N) time.

    curr = s[N];  // Current prime factor of N
    cnt = 1;   // Power of current prime factor

    // Printing prime factors and their powers
    while (N > 1)
    {
        N /= s[N];

        // N is now N/s[N].  If new N also has its 
        // smallest prime factor as curr, increment 
        // power and continue
        if (curr == s[N])
        {
            cnt++;
            continue;
        }

        // Print prime factor and its power
        print(curr, cnt);

        // Update current prime factor as s[N] and
        // initializing count as 1.
        curr = s[N];
        cnt = 1;
    }

Below is C++ implementation of above steps.

// C++ Program to print prime factors and their
// powers using Sieve Of Eratosthenes
#include<bits/stdc++.h>
using namespace std;

// Using SieveOfEratosthenes to find smallest prime
// factor of all the numbers.
// For example, if N is 10,
// s[2] = s[4] = s[6] = s[10] = 2
// s[3] = s[9] = 3
// s[5] = 5
// s[7] = 7
void sieveOfEratosthenes(int N, int s[])
{
    // Create a boolean array "prime[0..n]" and
    // initialize all entries in it as false.
    vector <bool> prime(N+1, false);

    // Initializing smallest factor equal to 2
    // for all the even numbers
    for (int i=2; i<=N; i+=2)
        s[i] = 2;

    // For odd numbers less then equal to n
    for (int i=3; i<=N; i+=2)
    {
        if (prime[i] == false)
        {
            // s(i) for a prime is the number itself
            s[i] = i;

            // For all multiples of current prime number
            for (int j=i; j*i<=N; j+=2)
            {
                if (prime[i*j] == false)
                {
                    prime[i*j] = true;

                    // i is the smallest prime factor for
                    // number "i*j".
                    s[i*j] = i;
                }
            }
        }
    }
}

// Function to generate prime factors and its power
void generatePrimeFactors(int N)
{
    // s[i] is going to store smallest prime factor
    // of i.
    int s[N+1];

    // Filling values in s[] using sieve
    sieveOfEratosthenes(N, s);

    printf("Factor Power\n");

    int curr = s[N];  // Current prime factor of N
    int cnt = 1;   // Power of current prime factor

    // Printing prime factors and their powers
    while (N > 1)
    {
        N /= s[N];

        // N is now N/s[N].  If new N als has smallest
        // prime factor as curr, increment power
        if (curr == s[N])
        {
            cnt++;
            continue;
        }

        printf("%d\t%d\n", curr, cnt);

        // Update current prime factor as s[N] and
        // initializing count as 1.
        curr = s[N];
        cnt = 1;
    }
}

//Driver Program
int main()
{
    int N = 360;
    generatePrimeFactors(N);
    return 0;
}
Factor  Power
  2      3
  3      2
  5      1

The above algorithm finds all powers in O(Log N) time after we have filled s[]. This can be very useful in competitive environment where we have an upper limit and we need to compute prime factors and their powers for many test cases. In this scenario, the array needs to be s[] filled only once.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/print-all-prime-factors-and-their-powers/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar