ACM学习历程20——竞赛中的简单数学问题之最大公约数、素数表、排列组合数

一、求解最大公约数和最小公倍数

#include<iostream>
using namespace std;

int main()
{
int a,b,t;
cin>>a>>b;
t=a>b?a:b;
for(;t>=1;t--)
{
if(a%t==0 && b%t==0)
break;
}
cout<<"The greatest common divisor:"<<t<<endl;
cout<<"The least common multiple:"<<a*b/t<<endl;
return 0;
}
测试：
6 4
The greatest common divisor:2
The least common multiple:12

这种方式是选择a和b中较大的数作为可能的最大公约数并赋值给t，若a和b能同时被t整除则t即为最大的公约数，但是这种方法的缺点也是明显的，例如：a为9999，b为1,那么t要从9999一直递减到1,，才能得到最大的公约数1，改进如下：

#include<iostream>
using namespace std;

int main()
{
int a,b,t;
int x,y;
cin>>a>>b;
x=a;y=b;
if(a<b)
{
t=a;
a=b;
b=t;
}
while(b!=0)
{
t=a%b;
a=b;
b=t;
}
cout<<"The greatest common divisor:"<<a<<endl;
cout<<"The least common multiple:"<<x*y/a<<endl;
return 0;
}
测试：
60 24
The greatest common divisor:12
The least common multiple:120

二、素数判断：

#include<iostream>
#include<cmath>
using namespace std;

bool Prime(int x)
{
int i;
for(i=2;i<=sqrt(x);i++)
if(x%i==0)
return false;
return true;
}

int main()
{
int x;
while(cin>>x)
{
if(x<=1)
cout<<"error"<<endl;
else
{
bool flag=Prime(x);
if(flag)
cout<<x<<" is prime"<<endl;
else
cout<<x<<" not prime"<<endl;
}
}
return 0;
}

对于要进行大量素数判断的情况可以先建立一张素数表：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=1000;
bool prime[N];

void initPrime()
{
//若为素数返回true,反之为false
fill(prime+2,prime+N,true);
for(int i=2;i<N;i++)
{
if(prime[i])
{
for(int j=i+i;j<N;j+=i)
prime[j]=false;
}
}
}

int main()
{
int x;
        initPrime();
while(cin>>x)
{
if(x<=1)
cout<<"error"<<endl;
else
{
if(prime[x])
cout<<x<<" is prime"<<endl;
else
cout<<x<<" not prime"<<endl;
}
}
return 0;
}

求组合数：从N个元素中选择M个元素，求解组合数：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int combination(int m,int n)
{
int i,ans=1;
for(i=1;i<=m;i++)
{
ans=ans*n;
n--;
}
for(i=2;i<=m;i++)
ans=ans/i;
return ans;
}

int main()
{
    int m,n;
while(cin>>m>>n)
{
cout<<combination(m,n)<<endl;
}
return 0;
}

求排列数：从N个元素中选择M个元素进行全排列：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int permutation(int m,int n)
{
int i,ans=1;
for(i=1;i<=m;i++)
{
ans=ans*n;
n--;
}
return ans;
}

int main()
{
    int m,n;
while(cin>>m>>n)
{
cout<<permutation(m,n)<<endl;
}
return 0;
}