Algotree > Algorithms > Numeric > Finding Prime Factors Of A Number

Finding Prime Factors Of A Number

What are prime numbers
A prime number ‘p’ is a natural number with only two factors, 1 and the number itself i.e p. i.e A prime number cannot be factorized into more than 2 natural numbers.
Example: 2, 3, 5, 7, 9,…

Properties of prime numbers

All prime numbers are odd except 2.
All prime numbers except 2 and 3 are of the form 6*n+1 or 6*n-1.
Example: 31 = 6 * 5 + 1
Example: 941 = 6 * 157 - 1
[Mersenne’s Primes] If a number of the form 2^n-1 is prime. Then ’n’ has to be a prime, but not the other way around.
Example: Number 31 is prime. It is of the form 2⁵-1, then 5 has to be prime which it is.
Example: Number 11 is prime. But that does not make 2¹¹-1 (2047) prime. 2047 is divisible by 23 and 89.

Prime factors of a number

A number can be factorized into its prime factors.
Consider the number 15, it can be factorized into 3¹ * 5¹.
Similarly the number 2310 can be factorized into 2¹ * 3¹ * 5¹ * 7¹ * 11¹.

Algorithm : Prime Factors ( N )

1.    Check if the number N has 2 as a prime factor.
      Do this by continuously dividing N by 2 and checking if the remainder is 0
2.   Check for odd prime factors of N
      Do this by continuously dividing N from 3 till SquareRoot(N) and checking if the remainder is 0
3.   Check if the value of N is still greater than 2
       If N is greater than 2, then N is a prime number with a power of 1.

Program for finding prime factors

import math
from dataclasses import dataclass

@dataclass 
class PrimeFactors :
        
    num : int 

    # Function to find all prime factors of a given number
    def Generate(self):
       cnt = 0 
       n = self.num
       # Check for factors of 2
       while n % 2 == 0 : 
           n /= 2
           cnt += 1

       if cnt :
           print("2^"+str(cnt), end=' ')
               
       # Check for odd prime factors
       for p in range(3, int(math.sqrt(n))+1, 2): 
           cnt = 0 
           while n % p == 0 : 
               n /= p
               cnt += 1
           if cnt :
               print(str(p)+"^"+str(cnt), end=' ')
       if n > 2 : 
           print(str(n)+"^1", end=' ')
 
def main() :
    n = int(input("Enter a number : "))
    p = PrimeFactors(n)
    p.Generate()
        
if __name__ == "__main__" :
    main()

Output

Enter a number : 2310
2^1 3^1 5^1 7^1 11^1

Enter a number : 7
7^1

Enter a number : 248
2^3 31^1

Enter a number : 1000
2^3 5^3

Enter a number : 999
3^3 37^1

#include<iostream>
#include<cmath>
using namespace std;

class PrimeFactors {

    private:
    int num;

    public:
    PrimeFactors(int arg_num):num(arg_num)
    {}

    // Function to find all prime factors of a given number
    void Generate() {

        int cnt = 0;

        // Check for factors of 2
        while ( num%2 == 0 ) {
            cnt++;
            num /= 2;
        }

        if (cnt)
            cout << "2^" << cnt << " ";

        // Check for odd prime factors
        for (int i=3; i<=sqrt(num); i+=2) {
            cnt = 0;
            while ( num%i == 0) {
                cnt++;
                num /= i;
            }
            if ( cnt )
               cout << i << "^" << cnt << " ";
        }

        // If the number is prime, it will have only 1 factor
        if (num > 2)
            cout << num << "^1";

        cout << endl;
    }
};

int main() {

    int N;
    cout << "Enter number : " ;
    cin >> N;
    PrimeFactors o(N);
    o.Generate();
    return 0;
}

Output

Enter number : 60
2^2 3^1 5^1

Enter number : 248
2^3 31^1

Enter number : 2310
2^1 3^1 5^1 7^1 11^1

import java.util.Scanner;

class PrimeFactors {

    public static void Generate(int n) {
  
        int cnt = 0;
  
        //check for factors of 2
        while (n%2 == 0) {
            cnt++;
            n = n/2;
        }
  
        if (cnt > 0) {
            System.out.print("2^" + cnt + " ");
        }
  
        //Check for odd prime factors
        //Note: n cannot have factors beyond sqrt(n)
        for (int i=3; i <= Math.sqrt(n); i+=2) {
  
            cnt = 0;
            while ( n%i==0 ) { 
                cnt++;
                n /= i;
            }
            if ( cnt>0 ) { 
                System.out.print(i + "^" + cnt + " ");
            }
        }
  
        //If the number is prime it will have only 1 factor
        if ( n > 2 ) { 
            System.out.print(n + "^1");
        }
  
        System.out.println();
    }   

    public static void main (String[] args) {
  
        int num;
  
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number : ");
  
        num = sc.nextInt();
        Generate(num);
    }   
}

Output

Enter number : 6
2^1 3^1

Enter number : 65536
2^16 

Enter number : 128
2^7 

Enter number : 46
2^1 23^1

Enter number : 36
2^2 3^2 

Enter number : 2310
2^1 3^1 5^1 7^1 11^1