Finding Prime Factors of a Number

September 28, 2022

What are Prime Factors?

Prime factors are factors of a number that are, themselves, prime numbers. There are many methods to find the prime factors of a number, but one of the most common is to use a prime factor tree.

For example, if the Input number is 12, then the Output should be [2, 2, 3]. And if the input number is 315, then the output should be [3, 3, 5, 7].

Finding Prime Factors of a Number

Finding Prime Factors of a Number in C++

Prime factors are basically the factors of the number input which are prime themselves. For instance the prime factors of “24”, without duplication, are [ 12, 2, 6, 3] but the Prime Factors, without duplication, are [ 2, 3]. The best way to find out the prime factors is to find the factors of the given number input and check whether they’re prime numbers or not. 

For instance, Let the input number be “315”. The factors of “315”, without duplication, are [ 63, 21, 5, 3, 7]. For Prime factors we will now check which of the following numbers are Prime number by dividing each number with all the number from 2 to square root of the current factor. If it’s divisible by any number other than itself, it’s not a prime. It’s  prime otherwise. Therefore the Prime Factors of “315”, Without duplication, are [ 5, 3, 7].

Finding Prime Factors of a Number C++

Power of a number

Factor of a number

Finding Prime Factors of a number

Strong number

Perfect number

Perfect Square

C++ Code

Run 
// C++ program to print all prime factors 
#include <bits/stdc++.h>
using namespace std;

void primeFactors(int n) 
{ 
    while (n % 2 == 0) 
    { 
        cout << 2 << " "; 
        n = n/2; 
    } 

    for (int i = 3; i <= sqrt(n); i = i + 2) 
    { 
        
        while (n % i == 0) 
        { 
            cout << i << " "; n = n/i; } } if (n > 2) 
        cout << n << " "; 
} 

// Driver code 
int main() 
{ 
    int n = 315; 
    primeFactors(n); 
    return 0; 
}

Output

3 3 5 7

Explanation

The objective is to factorize the given input number and print out all the prime factors of the input number. In order to do so we’ll perform multiple division operations  until the number can’t be divided any further.

The algorithm for the above code is as follows:

  1. Declare a void function primeFactors(int n) which takes an integer “n” as an argument.
  2. Check if the integer value “n” is divisible by 2. If true, keep dividing the number  until it’s not divisible by 2 using a while loop and print “2” after every iteration.
  3. Run a for loop from 3 to the square root of “n” and step size as 2 to avoid even numbers.
  4. Run a nested while loop and check for the divisibility of the number with i value. If divisible, print the “i” value and perform division.
  5. Check if the number is greater than 2. If true, print “n” using cout command.
  6. Call the function primeFactors(315) from the driver code section.

The output of the above code is a numeric string of all the Prime Factors of the input string “n”.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

7 comments on “Finding Prime Factors of a Number”


  • Sameer

    #include
    using namespace std;
    int main() {
    int num;
    cout<>num;
    while(num!=1){
    for(int i=2; i<=num; i++){
    if(num%i==0){
    cout<<i<<" ";
    num = num/i;
    break;
    }
    }
    }
    return 0;
    }


  • ROHAN

    #include
    using namespace std;
    int main() {
    int n,m=1;
    std::cin >> n;
    while(n%2==0){
    std::cout << 2<<" " ;
    n=n/2;}
    for(int i=3;i<=n;i=i+2){
    if(n%i==0){cout<<i<<" ";
    n=n/i;}
    else {continue;}
    }
    return 0;
    }


  • Sajeed

    #include

    using namespace std;
    bool isprime(int x){
    for(int i=2;i>n;
    for(int i=2;i<n;i++){
    if(n%i==0){
    if(isprime(i)){
    cout<<i<<' ';
    }
    }
    }
    }


  • Sajeed

    #include
    #include
    using namespace std;
    bool isprime(int x){
    for(int i=2;i>n;
    for(int i=2;i<n;i++){
    if(n%i==0){
    if(isprime(i)){
    cout<<i<<' ';
    }
    }
    }
    }


  • 358_Sanyogita

    #include
    #include
    using namespace std;
    bool isprime(int x)
    {
    if(x<2)
    {
    return false;
    }
    else{
    for(int i=2;i<x;i++)
    {
    if(x%i==0)
    return false;
    }
    }
    return true;
    }
    int main()
    {
    int n=315;
    if(n<2)
    {
    cout<<"no ";
    }
    else{
    for(int i=3;i<=sqrt(n);i++)
    {
    if(n%i==0 && isprime(i))
    {
    cout<<i<<" ";
    }
    }
    }

    return 0;
    }


  • VICKY

    #include
    #include
    using namespace std;
    void primeNo(int n){
    bool flag = true;
    if(n < 2){
    flag = false;
    }
    for(int j = 2; j <= sqrt(n); j++){
    if(n % j == 0){
    flag = false;
    break;
    }
    }
    if(flag == true){
    cout<<n<>n;
    for(int i = 1; i <= n; i++){
    if(n % i == 0){
    primeNo(i);
    }
    }
    return 0;
    }