CODEWITHSUNDEEP
c++
Humaid Kidwai
Humaid Kidwai

Reputation: 99

finding all prime factors of a number

This program calculates all factors of a no. by first finding all prime factors and adding 1 to their exponents and then multiplying them amongst each other. But in the for loop i is incremented by 2 in every iteration.Isn't this wrong as after 7 it'll be incremented to 9 which isn't prime? Or am I wrong? Can anyone pls explain!

#include<bits/stdc++.h>
using namespace std;

int main() 
{
    int n,i;
    cin>>n;
    int factors=1,exponen=0;//exponent stores power of current prime
    while(n%2==0)//a separate check for 2       {
        exponen++;
        n=n/2;
    }
    factors= factors*(exponen+1);
    exponen=0;
    int original_n=n;
    for(i=3;n>1 && i<=sqrt(original_n);i+=2)//Checking for every prime number
    {
        exponen=0;
        while(n%i==0)
        {
            exponen++;
            n=n/i;
        }
        factors= factors*(exponen+1);
    }
    cout<< factors<< endl;
    return 0;
}

Upvotes: 2

Views: 433

Answers (2)

Persixty
Persixty

Reputation: 8579

I'm not sure if it's computing or maths.

But if i is composite it will never divide the current value of n. That's because all the prime factors of the composite number i have already been visited and 'divided out' of n.

9 is a special case. Any factors of 3 have been divided out so n%i==0 will never be true by the time i reaches 9.

Similarly when it reaches 15 the factors of 3 and 5 have been divided out and n%15==0 will be false.

Upvotes: 0

Jean-Fran&#231;ois Fabre
Jean-Fran&#231;ois Fabre

Reputation: 140148

    while(n%i==0)
    {
        exponen++;
        n=n/i;
    }

that loop removes (and counts) all the i factors from n until there's none left.

So when you reach 9 you already removed all powers of 3, so 9 never divides n at this point: the algorithm works

Note: this method is not the most efficent one, looping on an actual prime number list generated using the sieve of Erathostenes could speed that up since there are no tests on every odd number, only on the primes (the loop cannot be as easily avoided, though)

Upvotes: 1

Related Questions