素数的查找和判断

浅浅的花香味﹌ 2023-09-23 13:27 60阅读 0赞

> 首先我们得先知道素数是什么？素数也就是质数，大于2的一个只能被自己整除的数，如2 、3、5 、7等；所以利用这个特点可以进行编程，从而查找素数，例如查找100--200之间的素数

#include<stdio.h>
    int main()
    {
    	int i = 0;
    	for (i = 100; i <= 200; i++)    //判断i是否为素数
    	{
    		
    		int flag = 1;//假设i是素数
    		int j = 0;
    		for (j = 2; j <= i - 1; j++)    //拿2~i-1之间的数字试除
    		{
    			if (i % j == 0)
                  {
    				flag = 0;     //当可以被整除时，则不是素数
    			break;
    			}
    		}
    		if (flag == 1)
    		{
    			printf("%d ", i);
    		}
    	}
    	return 0;
    }

> *该程序则是每一个数m都需要用2到m-1整除；一一试探，但是如果我试探少一点呢？很简单，一个数m的开平方![b370329d63e2c585884fb48762036878.gif][]，若是用m÷（2——![b370329d63e2c585884fb48762036878.gif][]）可以整除，则不是素数，反而则是素数。原因呢？*
> 
> *因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 ![b370329d63e2c585884fb48762036878.gif][]，另一个大于或等于 ![b370329d63e2c585884fb48762036878.gif][]* 如：16，可以被2、 4、8 整除，16开平方等于4，而4\*4=16,2\*8=16，所以很明显因子里必有一个小于*![b370329d63e2c585884fb48762036878.gif][]*

#include <math.h>    //sqrt的头文件
    #include<stdio.h>
    int main()
    {
        int i = 0;
    	for (i = 100; i <= 200; i++)
    	{
    		
    		int flag = 1;//假设i是素数
    		int j = 0;
    		for (j = 2; j <= (int)sqrt(i); j++)//强制转换，且拿2--√￣i
    		{
    			if (i % j == 0)
    			{
    				flag = 0;
    				break;
    			}
    		}		
               if (flag == 1)
    		{
    			printf("%d ", i);
    	  }
    	}
    	return 0;
    }

> 还有更简单的，当素数大于2时，素数一定不会是偶数，而奇数不一定是素数，但是素数一定是奇数，所以可以又简洁一点。

#include<stdio.h>
    #include<math.h>
    int main()
    {
    	int i = 0;
    	for (i = 101; i <= 200; i+=2)//每次加2，跳过偶数，直接判断奇数
    	{
    		
    	    int flag = 1;//假设i是素数
    		int j = 0;
    		for (j = 2; j <= (int)sqrt(i); j++)
    	    {
    		if (i % j == 0)
    			{
    				flag = 0;
    				break;
    			}
    		}
    		if (flag == 1)
    		{
               printf("%d ", i);
    		}
    	}
    	return 0;

[b370329d63e2c585884fb48762036878.gif]: https://img-blog.csdnimg.cn/img_convert/b370329d63e2c585884fb48762036878.gif