# Finding Prime Factors Of A Number

## Finding all 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 = 65+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^5-1, then 5 has to be prime which it it.
Example: Number 11 is prime. But that does not make 2^11-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^1 * 5^1.
Similarly the number 2310 can be factorized into 2^1 * 3^1 * 5^1 * 7^1 * 11^1.

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.

C++

C++ : Finding all prime factors of a number. Implemented in C++14

Python : Finding all prime factors of a number. Implemented in Python 3.7 using dataclass

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