C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 



Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old April 2nd, 2005, 07:48 AM
mysticorphan mysticorphan is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Apr 2005
Posts: 2 mysticorphan User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 27 m 4 sec
Reputation Power: 0
C++ Calculating prime factors

This has been puzzling me for quite some time, and i've tried making up code to work but it seems i always double up on some numbers.

Well this is the question:

here "a" and "b" are any integers.
(A) Calculate and output the number of the different prime factors of a. A prime factor of n is a factor of n which is a prime number. A prime number is any integer greater than 1 and only divisible by itself and 1 (e.g. 2, 3, 5, 7, 11, 13, 17 etc).

(B) Calculate and output the largest prime factor of a.

(C) Calculate and output the greatest common divisor (gcd) of a and b. The gcd of two integers m and n is the largest integer which divides both m and n.

So for example:
a=24 b = 36
1, 2, 3, 4, 6, 8, 12, 24 are divisors of 24.

1, 2, 3, 4, 6, 8, 9, 12, 18, 36 are divisors of 36.

12 is the gcd of 24 and 36.


i can't get pass (A)
this is the code i have so far.

int a, i, g, no_prime, o;
i = 0;
g = 0;
no_prime= 0;

cin>>a;
cout<<endl<<"a is "<<a<<endl;

for (i=2; i<=a; i++)
{
if ((a%i)==0)
{
a=(a/i);
for (g = 2; g<=i; g++)
{
if ((i % g) == 0)
{
o=1;
no_prime++;
cout<<"no of prime "<<no_prime<<endl;
}

}
}
}
cout<<"no of prime "<<no_prime<<endl;




The problem is it seems to double up on 2's and etc. *sigh* i've hit my brain a million times. is there something to overcome this?



Reply With Quote
  #2  
Old April 4th, 2005, 01:51 PM
SeanJA101 SeanJA101 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Mar 2005
Posts: 6 SeanJA101 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 2 h 27 m 43 sec
Reputation Power: 0
If you haven't gotten it yet here is a way that you can do the first part:

Code:
#include <stdio.h>
     #include <iostream.h>
     
     main()
     {
     	
     	int a, i, g, no_prime, o=0;
     	i = 0;
     	g = 0;
     	no_prime= 0;
     	cout<<"Enter a number:";
     	cin>>a;
     	cout<<endl<<"The number is "<<a<<endl;
     	for (i=2; i<=a; i++)
     	{
     
     		if (a % i == 0)
     		{
 			cout << i << " is a factor of " << a << endl;
     			++o;
     		}
     	}
     	if (o == 1)
     		cout << "The number " << a <<" is prime\n";
     	else
     		cout << "The number " << a <<" is not prime\n";
     	return 0;
     }


Which results in the output of (using your 2 examples):

Code:
a)Enter a number:36
    
    The number is 36
    1 is a factor of 36
    2 is a factor of 36
    3 is a factor of 36
    4 is a factor of 36
    6 is a factor of 36
    9 is a factor of 36
    12 is a factor of 36
    18 is a factor of 36
    36 is a factor of 36
    The number 36 is not prime
    Press any key to continue
    
    b)Enter a number:24
   
   The number is 24
   1 is a factor of 24
   2 is a factor of 24
   3 is a factor of 24
   4 is a factor of 24
   6 is a factor of 24
   8 is a factor of 24
   12 is a factor of 24
   24 is a factor of 24
   The number 24 is not prime
   Press any key to continue
   



I think that you were trying to make it too difficult for starters... all you need to do now is figure out the last part, which shouldn't be too tough I hope

Good luck,

--Sean Sandy


Hmmm... I found a problem with the code that I posted... it always says that the number is not prime... trying to fix that now...

Fixed it, (always remember to initialize your variables :P) stupid mistake... hehehe

Reply With Quote
  #3  
Old May 15th, 2005, 04:39 AM
justin_fortmann justin_fortmann is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: May 2005
Location: Durban, South Africa
Posts: 1 justin_fortmann User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 2 m 12 sec
Reputation Power: 0
Send a message via MSN to justin_fortmann
Calculating Prime Factors

Here is my version of the algorithm (that works).

Code:
 
void printPrimeFactors(int number)
{ 
	 stack<int> primeStack;
	 assert(number >= 0);
	 for(int i = 2; i <= number; i++) // Test for factors > 1
	 {
		 if(number % i == 0) // It is a factor > 1
		 {
			 bool prime = true;
			 for(int j = 2; j < i; j++) // Test for prime
			 {
				 if(i % j == 0) // It is not prime
					 prime = false;
			 }
			 if(prime)
				 primeStack.push(i);
		 }
	 }
	 while(!primeStack.empty())
	 {
		 cout << primeStack.top() << endl;
		 primeStack.pop();
	 }
}


Justin Fortmann

Reply With Quote
  #4  
Old July 5th, 2005, 07:15 AM
anki607 anki607 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jul 2005
Posts: 4 anki607 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 8 m 2 sec
Reputation Power: 0
Simple solution

Here is a simple solution to ur problem part (A) and (B):


Code:

#include <iostream.h>

void PrimeFactors (int );


int main()
{
	int n = 0;
	cout<<"\t\tWelcome to Prime Factors program\n\n";
	cout<<"Enter the number : ";
	cin>>n;
	cout<<"\n\n";
	PrimeFactors(n);
	
	return 0;
}

void PrimeFactors (int n)
{
	
	int count = 0;
	int temp = 0;
	
	
	for ( int i = 1 ; i <= n ; i++ )
	{
		
		int j = i - 1;
		
		while ( j > 1 )
		{
			if ( i % j == 0 )      //Is PRIME
				break;
			else
				j--;
		}
		
		if ( j == 1 )
		{
			if ( n % i == 0 )
			{
			 cout<<"\n"<<i;    //PRIME factor 
				
				if ( i > temp )
		                          {	temp = i;
				             count++;
                                                     } 
			}
		}
		
	}

	cout<<"\n\nNumber of prime factors of "<<n<<" : "<<count<<"\n\n";
	cout<<"Greatest prime factor is "<<temp<<"\n\n";
}}

Reply With Quote
  #5  
Old July 6th, 2005, 04:10 PM
anki607 anki607 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jul 2005
Posts: 4 anki607 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 8 m 2 sec
Reputation Power: 0
Full solution to ur problem

Code:
//Program to find prime factors of a specified number and greatest prime factor.


#include <iostream.h>
#define COUNT 50

void PrimeFactors (int );
void GCD ( int , int );

int main()
{
	int a,b;
	
	cout<<"\t\tWelcome to Prime Factors\Factors\GCD program\n\n";
	cout<<"Enter first number a : ";
	cin>>a;
	cout<<"\n\nEnter second number b : ";
	cin>>b;
	cout<<"\n\n";
	
	GCD(a,b);
	PrimeFactors(a);
	PrimeFactors(b);
	
	return 0;
}

void PrimeFactors (int n)
{
	
	int count = 0;
	int temp = 0;
	//int GrtPr[];
	
	for ( int i = 1 ; i <= n ; i++ )
	{
		
		int j = i - 1;
		
		while ( j > 1 )
		{
			if ( i % j == 0 )      //Is PRIME
				break;
			else
				j--;
		}
		
		if ( j == 1 )
		{
			if ( n % i == 0 )
			{
												
				cout<<"\n"<<i;    //PRIME factor 
				
				if ( i > temp )
					temp = i;
				//GrtPr[count] = i;
				count++;
			}
		}
		
	}

	cout<<"\n\nNumber of prime factors of "<<n<<" : "<<count<<"\n\n";
	cout<<"Greatest prime factor is "<<temp<<"\n\n";
		
}




void GCD ( int a, int b )
{
	int x [COUNT];
	int y [COUNT];
	
	
	//Factors of a.

	int counta = 0;
	
	for ( int i = 1 ; i <= a ; i++ )
	{
		
		if ( a % i == 0 )
		{
			cout<<"\n"<<i;     //Is Factor 
			x[counta] = i;
			counta++;

		}
		
	}

	cout<<"\n\nNumber of factors of "<<a<<" : "<<counta<<"\n\n";

	//Factors of b.

	int countb = 0;
	
	for ( int j = 1 ; j <= b ; j++ )
	{
		
		if ( b % j == 0 )
		{
			cout<<"\n"<<j;     //Is Factor 
			y[countb] = j;
			countb++;
		}
		
	}

	cout<<"\n\nNumber of factors of "<<b<<" : "<<countb<<"\n\n";


	//GCD from the factors of a and b.

	cout<<"\n\nCommon factors of "<<a<<" and "<<b<<" are : \n\n"; 
	int k = 0;
	
	for ( i = 0 ; i < counta ; i++ )
	{
		for ( j = 0 ; j < countb ; j++)
		{
			if ( x[i] == y[j] )
			{
				if ( x[i] > k )
					k = x[i];
				cout<<x[i]<<"\n";
			}
		}
	}
	
	cout<<"\n\nGreatest Common Divisor (GCD) of "<<a<<" and "<<b<<" is : "<<k<<"\n\n";
}

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > C++ Calculating prime factors


Developer Shed Advertisers and Affiliates


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap