dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: counting prime divisors

  1. #1
    Join Date
    Apr 2018
    Posts
    1

    Unhappy 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. #2
    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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)