In other words, prime factors are determined by finding which prime numbers multiply together to form the original number. Example: Prime Factors of 10 are 2 and 5. This is because 2X5 =10 and both 2,5 are prime numbers.
Finding the Prime Factors using Iteration
To find the prime factors of a given number, we first iterate over all the numbers from 2 until the square root of the number, and then check if each number is prime. As long as the original number is dividable by this prime, we keep adding this prime with each iteration. Example: Every prime number greater than 40 is written in the following formula: n2+n+41. So, we can substitute n with all the numbers to find the corresponding prime factor. e.g., 02+0+41=41, 12+1+41=43, 22+2+41=47,…
How to print a prime factor of a number?
In this method, we will be iterating over the numbers from 2 until the square root of the number, as mentioned in the previous section. For that, we need to check the modulus of the original number on each of the numbers from 2 until the square root of n . Then, we find the list of prime numbers that are factors of n. This solution is in O(Sqrt(n)) time complexity.
Algorithm:
Set a counter i to 2
While i <= sqrt(n):
While n% i == 0:
n = n / i
print i
i = i +1
if n > 1:
print n
Sieve Algorithm
Sieve method relies on storing the smallest prime factor of the numbers, which reduces the complexity noticeably when calculating the prime factors for any number. Sieve algorithm finds all the prime factors somewhat efficiently.
The main concept of this algorithm is to store the smallest prime factor of each number until the maximum number. We take the smallest prime for each given number and add it to the set of prime factors. Finally, we divide by this prime number and repeat these steps until we reach 1. This is all done in O(log(n)) time complexity, improving the solution’s efficiency a lot. Which makes it possible to calculate the prime factors of much larger numbers than the ones we could have dealt with using the previous approach.
Example: The second way is to check if the number can be written as 6n-1 or 6n+1 as any prime number other than 2 and 3 should be written in one of the two formulas. e.g., 5=6(1)-1, 19=6(3)+1,… . Algorithm: Define an array array to store the smallest prime factor of each number with the index value as an initial value for every element of the array.
Set array[1] to 1 Set i to 2 While ii > max number: If array[i] == i: Set j to ii While j > max number: If array[j] == j: Array[j] = i j = j + i i = i + 1 while the number != 1: print array[the number] the number = the number / array[the number]
Python Prime Factors Using Iteration
Here, we will be showing a code in Python language to find the prime factors of a given number in an iterative method:
import math def PrimeFactors(n): for i in range(2,int(math.sqrt(n))+1,1): while n%i==0:#find all the occurrences of a prime factor print((int)(i)), n=n/i if n!=1:#if the number was originally a prime print((int)(n)) n=(int)(input(“Enter the number you want: “)) PrimeFactors(n)
Output:
Enter the number you want: 4 4
Python Prime Factors Using Recursion
This section shows a code in Python language using the sieve method to find the prime factors of a given number.
import math High = (int)(1e5+7) array=[0 for i in range(High)]
function to generate all the smallest prime
def Sieve(): #factors of the numbers until the maximum number for i in range(1, High): array[i]=i for i in range(2, math.ceil(math.sqrt(High))): if (array[i] == i): for j in range(i*i, High,i): if(array[j]==j): array[j]=i def PrimeFactors(n): #We will keep dividing until we reach 1 if n == 1: return print((int)(array[n])) PrimeFactors((int)(n/array[n])) #Here we call the function after dividing it by this prime Sieve() n=(int)(input(“Enter the number you want: “)) PrimeFactors(n)
Output:
Enter the number you want: 4 2 2
C Prime Factors Program Using Iteration
It is the same solution as the iterative python one but written in C language. We ask the user to enter the number, then for each number from 2 to the square root of this number, we need to check if it’s dividable by printing all the occurrences of this factor.
#include <stdio.h> int main() { int n; printf(“Enter the number you want: “); scanf("%d”, &n); for(int i=2; i*i<=n; i++) { while(n%i==0)//find all the occurrences of a prime factor { printf("%d\n”,i); n/=i; } } if(n!=1)//if the number was originally a prime { printf("%d”,n); } return 0; }
Output:
Enter the number you want: 2 2
C Prime Factors Program Using Recursion
This is the same solution as the python recursive one but written in C. We can ask the user to enter the number; then, we build the primes array that stores the smallest prime factor of each number. Finally, we call the Prime Factors recursive function, which divides the given number by its smallest prime factor and recalls itself until reaching one.
#include <stdio.h> int Max = 100007; int array[100007]; void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number { for(int i=1;i<Max;i++) { array[i]=i; } for(int i=2;ii<=Max;i++) { if(array[i]==i) { for(int j=ii;j<Max;j+=i) { if(array[j]==j) { array[j]=i; } } } } } void PrimeFactors(int n) { if(n==1)//keep dividing until we reach 1 { return; } printf("%d\n”,array[n]); PrimeFactors(n/array[n]);//call the function after dividing by //this prime } int main() { Sieve(); int n; printf(“Enter the number you want: “); scanf("%d”, &n); PrimeFactors(n); return 0; }
Output:
Enter the number you want: 2 2
Some interesting facts about Prime numbers:
One of the most interesting facts is that any even number other than 2 can be the sum of two prime numbers. For example: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … etc. Another fact is that there are no consecutive primes other than 2 and 3, as the only even prime number is the number 2. Also, all the prime numbers except 2 and 3 can be written in the following form: 6 * n + 1 or 6 * n – 1, where n is a positive integer. The set of prime factors of a number is a unique one. Number 1 is neither prime nor composite. Prime factorization of numbers can help solve problems like divisibility, simplifying fractions, and finding common denominators of different fractions. Also, one of the exciting uses of prime factorization is breaking secret codes that are number based.
