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 = 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^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

Copyright © 2019-2020, Algotree.org.
All rights reserved.