CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: counting prime divisors

1. Junior Member
Join Date
Apr 2018
Posts
1

## counting prime divisors

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.
Code:
```#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.";
}```

2. Elite Member Power Poster
Join Date
Jan 2006
Location
Singapore
Posts
6,749

## Re: counting prime divisors

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:
Code:
`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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width