转载请注明出处：http://blog.csdn.net/u010734277
这是我的第一篇技术博客，写的很浅，相信我会慢慢变强。
首先是欧几里得算法求最大公约数。
主要用到了辗转相除法，先用大的数除以小的数，得到余数，然后再用除数除以余数，再得余数……直到余数为0时，最后一步的除数就是所求最大公约数。
代码：
#include<iostream>
using namespace std;
int main(){
int swap(int &a,int&b);
int m,n;
cin>>m>>n;
if(n>m){ //number m must larger than n
swap(m,n);
}
int c;
for(c=m%n;c!=0;c=m%n){
m=n;
n=c;
}
cout<<n;
return 0;
}
void swap(int &a,int &b){
int t;
t=a;
a=b;
b=t;
}
下面是筛法求素数。
首先确定2是素数，然后就把2当作筛子，把2的倍数全部删掉。接着，确定三是素数，然后把3的倍数全部删掉。四为合数已经被删了。接下来是5……
下面是代码，相对于上面理论有改进的地方。
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int N; cin>>N;
int *Location=new int[N+1];
for(int i=0;i!=N+1;++i)
Location[i]=i;
Location[1]=0;
int p,q,end;
end=sqrt((double)N)+1;
for(p=2;p!=end;++p)
{
if(Location[p])
{
for(q=p;p*q<=N;++q)
{
if(Location[q])
{
for(int k=p*q;k<=N;k*=p)
{
Location[k]=0;
}
}
}
}
}
int m=0;
for(int i=1;i!=N+1;++i)
{
if(Location[i]!=0)
{
cout<<Location[i]<<" ";
++m;
}
if(m%10==0) cout<<endl;
}
cout<<endl<<m<<endl;
return 0;
}
首先，是对于最后一个数，选择了根号n，因为n开方以后的和数必定已经被删了。证明这一点：n可以表示成end^2那么，把end*（end-1）就可以表示比n小一点的和数，以此类推，比end大的和数全部都能被表示。
接下来是q作为标记，把q*p到q*（p^z)都给删了。这样的一个好处是同一个数字不会被重复删除两次。比如在最前面的理论中，6会被2删一次，又被3删一次。在优化后的算法中，6只会被2删一次。