


Dev Articles Community Forums
> Programming
> C/C++ Help

C++ Calculating prime factors
Discuss C++ Calculating prime factors in the C/C++ Help forum on Dev Articles. C++ Calculating prime factors C/C++ Help forum discussing building and maintaining applications in C/C++. Find out why these languages are the foundation on which other languages are built.






Dev Articles Community Forums Sponsor:


April 2nd, 2005, 07:48 AM

Registered User


Join Date: Apr 2005
Posts: 2
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?

April 4th, 2005, 01:51 PM

Registered User


Join Date: Mar 2005
Posts: 6
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

May 15th, 2005, 04:39 AM

Registered User


Join Date: May 2005
Location: Durban, South Africa
Posts: 1
Time spent in forums: 2 m 12 sec
Reputation Power: 0


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

July 5th, 2005, 07:15 AM

Registered User


Join Date: Jul 2005
Posts: 4
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";
}}

July 6th, 2005, 04:10 PM

Registered User


Join Date: Jul 2005
Posts: 4
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";
}

Developer Shed Advertisers and Affiliates
Thread Tools 
Search this Thread 


Display Modes 
Rate This Thread 
Linear Mode


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off




