信息学奥赛一本通：2030：【例4.16】找素数

输出正整数a到b之间的所有素数。

输入a,b。

由小到大，输出a到b之间的所有素数。每个数占一行。

【数据范围】

对于所有数据，1≤a≤b≤20000。

【参考一】

思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int L,H;
	bool sushu=false;
	cin>>L>>H;
    for (int i=L; i<=H; i++)
    {
    	sushu=true;
    	for(int j=2;j<L;j++)
    	{
	    	if (i%j==0)
			{
				sushu=false;
				break;	
			}	
		}
    	if(sushu)
    	{
    		cout<<i<<endl; 
		}
    	
	}
    return 0;
}

【参考二】

思路2)：另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~?之间的每一个整数去除就可以了。如果 m 不能被 2 ~?间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。

原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于?，另一个大于或等于?。例如 16 能被 2、4、8 整除，16=2*8，2 小于 4，8 大于 4，16=4*4，4=，因此只需判定在 2~4 之间有无因子即可。

#include <bits/stdc++.h>
using namespace std;
int main ()
{
	int L,H,x;
	cin>>L>>H;
	for (int i=L;i<=H;++i)
  	{
     x=2;
     while(x<=floor(sqrt(i))&&(i%x!=0))//floor为取整函数，需调用math.h库
	 {
	    x=x+1;                       //在枚举的范围内并且没有出现约数则继续枚举	
	 }    

     if ( x>floor(sqrt(i)))
     {
     	cout<<i<<endl;
	 }
       
  	}	

  return 0;
}