# 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 2n-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 25-1, then 5 has to be prime which it is.
Example: Number 11 is prime. But that does not make 211-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 31 * 51.
Similarly the number 2310 can be factorized into 21 * 31 * 51 * 71 * 111.

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
``````