prime.cpp

此程序为求两个数的约数,将他们输出,将这两个数的最大公约数输出

#include <iostream>
#include "intentry.h"
#include <list>
using namespace std;
void loadPrimes(list<intEntry>& primes, int n)
{
	int i=2; //initialize the divided number to 2
	int nc=0;  //initialize the nc number for the same i as 0
	do  
	{
		if(n%i==0) //n can divide i without remainder
		{
			nc++; //the number of the divider i
			n=n/i;
		}
		else  //n divides i with remainder
		{
			if(nc>0)  
				primes.push_back(intEntry(i,nc));//push intEntry node into primes 
			nc=0; //clear the nc to 0 to continue division
			i++;//n divide i++, to divide the next following i
		}
	}while(n>1||nc!=0); //the input number n>1, nc!=0
}
void gcd(int m,int n)
{
	int i=2;
	int t=1;
	cout<<"gcd("<<m<<","<<n<<")=";
    while(m/i!=0&&n/i!=0)
	{
		if(m%i==0&&n%i==0)
		{
		    m=m/i;
		    n=n/i;
		    t=t*i;
		    cout<<i;
		}
        while(m/i!=0&&n/i!=0)
		{ 
            if(m%i==0&&n%i==0)
			{
		        m=m/i;
		        n=n/i;
		        t=t*i;
				cout<<"*";
		        cout<<i;
			}
			else i++;
		}
    }
	cout<<"="<<t;
}
void main()
{
    int m,n;
	cout<<"Please input two integer numbers m and n: "<<endl;
	cin>>m>>n;
	list<intEntry> primes1,primes2,primes3;
	list<intEntry>::iterator iter1,iter2;
	loadPrimes(primes1,m);
	cout<<m;
	for(iter1=primes1.begin();iter1!=primes1.end();iter1++)
		cout<<": "<<*iter1<<" ";
	loadPrimes(primes2,n);
	    cout<<endl;
	    cout<<n;
	for(iter2=primes2.begin();iter2!=primes2.end();iter2++)
		cout<<": "<<*iter2<<" ";
	    cout<<endl;
	for(iter1=primes1.begin();iter1!=primes1.end();iter1++)
		for(iter2=primes2.begin();iter2!=primes2.end();iter2++)
		if(operator==(*iter1,*iter2))
		{
			if(operator<(*iter1,*iter2))primes3.push_back(*iter1);
			else primes3.push_back(*iter2);
		}
	cout<<"The greatest common divider: "<<endl;
	for(iter1=primes3.begin();iter1!=primes3.end();iter1++)
		cout<<*iter1<<" ";
    gcd(m,n);
	cout<<endl;
}