counting prime divisors

[abir50]

I am trying to count the number of prime divisors for example prime divisors of 20 is 2*2*5 which is 3. The number of primes seem to be right sometimes.

#include <iostream>
#include <cmath>
using namespace std;

void prime_divisor(int n){
	int d=2;
	while(d<=sqrt(n)){
		if(n%d==0){
			cout<<d<<"*";
			n=n/d;
			continue;
		}
		++d;
	}
	cout<<n<<endl;
}

int prime_decomposition_r(int n){
    int count=0;
	for(int d=2; d<=sqrt(n); ++d){

		if(n%d==0){
			++count;
		}
	}
	return count;
	cout<<count<<endl;
}

int main(){
	int n=0;
	cout<<"n: ";
	cin>>n;
	cout<<"Type a positive integer:"<<n<<endl;
	cout<<n<<"=";
	prime_divisor(n);
	cout<<"There are "<<prime_decomposition_r(n)<<" prime factors.";
}

[laserlight]

Since you are already printing out the prime divisors in prime_divisor, and then effectively repeating the work for prime_decomposition_r, I suggest having a single function:

int prime_decomposition(int n);

This function would do the process you currently have for prime_divisor, but as it prints the prime divisors, it also counts them, returning the count in the end that you can print from main.

The issue you have with prime_decomposition_r now is that it only counts distinct prime divisors, whereas you want to count repeated prime divisors.

You can potentially improve the process you are using for prime_divisor:

• Treat the divisor 2 separately, so then you start the loop from 3, allowing you to jump by 2 instead of incrementing the test divisor.
• Instead of always computing d <= sqrt(n) where n might change on each iteration, it might be better to compare d * d <= n.