|
|||||||||
|
|||||||||
|
|||||||||
| |
|||
 |
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Display Modes |
Dev Articles Community Forums Sponsor:
|
|
|
|
#1
April 2nd, 2005, 07:48 AM
|
|||
|
|||
|
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?
|
|
#2
April 4th, 2005, 01:51 PM
|
|||
|
|||
|
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
|
|
#3
May 15th, 2005, 04:39 AM
|
|||
|
|||
|
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
|
|
#4
July 5th, 2005, 07:15 AM
|
|||
|
|||
|
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";
}}
|
|
#5
July 6th, 2005, 04:10 PM
|
|||
|
|||
|
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";
}
|
|
| Viewing: Dev Articles Community Forums > Programming > C/C++ Help > C++ Calculating prime factors |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
