西北政法大学校长换届:用c++编程 求3—100之间的素数

求素数的问题，尤其是求某个数下所有的素数的问题，具有一定的普遍性。对于这种“求 xx 下所有素数的问题”需要注意几点，就可以得到最优的快速算法。

（1）求某个数n的素数，只需要判断n 是否可以被2~sqrt(n)之间的数整除（包括2；如果sqrt（n）是整数，也包括它）。如果没有被整除的，则是素数。

为什么是到sqrt(n)，而不是取n下所有的数？这是因为，对于一个数n来说，如果它有一个非1 和非它本身的因子，那么n必然有两个因子，其中的一个较小的因子，假定这个因子为m，它的取值范围必定在1<m<=sqrt(n)。当且仅当这两个因子相等的时候，取上面的等号。
如果你在（1,sqrt(n)]找不到n的整数因子，你一定也不会在[sqrt(n),n)中找到n的整数因子。

（2）在（1,sqrt(n)]中，没有必要用每一个整数去试试是否能整除n。而是只用这个范围之间的素数就可以了。因为任何一个和数都可以分解为几个素数的积。因此，在计算这种“求小于n的所有的素数”问题时，就有必要存储下来已经计算出来的素数，可以减少以后进行%运算的次数。当n很大的时候，这种方法就显示出优势了，只是要多去开销一些内存空间。

一句话，用(1,sqrt(n)]之间的素数去判断一个数n是否为素数。

代码如下：

#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
int num = 100; //求num以下所有的素数
int i,j,i_prime = 0;
int primevector[50] = {0}; //用于存储已经计算出来的素数,要用足够大的空间来存储所有的素数,对于100来说,50已经足够了

//首先在primevector中记录下前两个素数2 , 3, i_prime是此数组中质数的个数
primevector[i_prime++] = 2;
primevector[i_prime++] = 3;

for(i=4;i<num;i++) //分别计算i 是不是素数
{
bool isprime = true;
float ftemp = sqrt(i);
//判断 i 是否为素数
for(j=0;primevector[j] <= ftemp;j++)
{
if(i % primevector[j] == 0)
{
isprime = false;
break;
}
}
//如果 i 是素数，则保存到primevector之中
if(isprime)
primevector[i_prime++] = i;

}

//输出所有的素数
for(i = 0;i<i_prime;i++)
cout<<primevector[i]<<' ';
cout<<endl;

return 0;
}

运行结果如下：
C:\Users\pc>notepad sushu.cpp

C:\Users\pc>g++ -o sushu.exe sushu.cpp

C:\Users\pc>sushu.exe
3—100之间的素数,素数如下
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
#include <iostream>
using namespace std;
int main()
{
 int arr[101];
 int i, j;
 for(i = 1; i < 101; i++)
  arr[i] = 1;
 for (i = 2; i < 101; i++)
 {
  if(arr[i]!=0)
   for (j = i+1; j< 101;)
   {
    if(j%i==0)
     arr[j] = 0;
    j = j+1;
   }
 }
cout<<"3—100之间的素数,素数如下\n";
 for(i = 3; i < 101; i++)
  if (arr[i]!=0)
   cout << i << " ";
 return 0;
}

#include<math.h>
#include <stdio.h>

main()
{
int i,j,n,a[101];
for( i=1; i<=100; i++)
a[i]=i;
for(i=2;i<sqrt(100); i++)
for(j=i+1; j<=100; j++)
{
if(a[i]!=0&&a[j]!=0)
if(a[j]%a[i]==0)a[j]=0;
}
printf("\n")
for(i=2,n=0; i<=100;i++)
{
if(a[i]!=0)
{printf("%d",a[i]);
n++;}
if(n==10)
printf("\n");
}
}

/****************************************/
#include<iostream>
/****************************************/
using namespace std;
/****************************************/
int main()
{
int i,k,n;
for(i=3;i<=100;i++)
{
for(k=2;k<=i;k++)
{
if(i%k==0)
{
break;
}
}
if(i==k)
cout<<i<<" is a prime.\n";
else
cout<<i<<" isn't a prime.\n";
}
return 0;
}
/****************************************/