【C语言】夏日一题 —— 如何判断素数?

作者:凡人编程传
系列:夏日一题 — 刷题专栏
说明:这个夏天，带你逆袭！

*前言

今天我们来研究判断素数的方法。开始之前先了解了解素数是什么？素数即是质数，这种数字只能被1和本身整除。注意，1不是素数。

*试除法(初级)

题目:求100-200的素数

我们知道了素数的概念，那么他的特点是只能被1和本身整除。那么我们在进行判断不是素数的时候是不是就有了一个确定的范围。假设判断n是不是素数,那么这个判断不是素数范围就是从2开始到n-1.然后在这个范围拿n与2到n-1的数字进行试除，如果n在这个范围内被整除，说明n一定不是素数。有了以上思路我们就可以写代码了:

#include<stdio.h>
int main()
{
    
	int i = 0;
	for (i = 100; i <= 200; i++)
	{
    
		int j = 0;
		for (j = 2; j < i; j++)
		{
    
			if (i % j == 0)
			{
    
				break;		//如果在2到i-1这个范围内被其中一个数整除了那么这个数字一定不是素数，也不用再进行后面的循环试除.
			}
		}
		if (j == i)			//来到这里的if语句有两种情况
		{
    					//1.上面在2到i-1范围中进行循环试除满足i%j==0条件然后执行break语句跳出内层循环来到这里
							//2.上面在2到i-1范围中进行循环试除没有满足i%j==0条件知道j<i这个条件为假(即是j==i)跳出内层循环,这时候不在这个范围没被整除的数字一定是素数。此时j==i.
			printf("%d是素数\n",i);		
		}
	}
	return 0;
}

运行结果:

*试除法(中级)

这时候你三下五除二写出代码兴致勃勃把代码交给面试官，面试官看了看面不改色道:还能再优化吗？这时候基础不牢固的同学就完了，所以咱们写一道题目一定要去多想另外的方法，不要只限于一种方法。

这种方法我们引出数学领域的知识:
一个数m肯定能写出m=a * b两个因子相乘的形式，而其中的至少有一个因子是小于等于开平方m的。例如16=2 * 8或者16=4 * 4,其中因子2<=4(开平方16),4<=4(开平方16)。通过这个我们可以得到，这里假设判断n是不是素数,如果n在2<=开平方n这个范围内被整除那么这个数字一定不是素数。这样我们的效率就提升了。那么这里素数也可以写成m=a * b的形式,如13=1 * 13有的人会说素数不也满足至少有一个因子是是小于等于开平方m的吗？但可以发现素数只能写成m=1 * m的形式，而其中因子1是不在我们循环试除判断范围2到开平方n之内的，而另外一个因子13>开根号13,所以素数也就不能在2到开平方n之间试除而导致矛盾。

这里我们还要借助MSDN了解一个函数：sqrt（）开平方函数。

由图可知，这个函数的功能是计算平方根，也就是开平方一个数。他的返回值类型是double,参数类型也是double.他所属头文件是<math.h>用的时候要包含一下。我们用这个函数作为循环条件(关系表达式)时候，最好能把它强制转换int类型，因为内层循环控制变量是int类型。

代码如下:

#include<stdio.h>
#include<math.h>
int main()
{
    
	int i = 0;
	for (i = 100; i <= 200; i++)
	{
    
		int j = 0;
		for (j = 2; j <= (int)sqrt(i); j++)
		{
    
			if (i % j == 0)
			{
    
				break;		//如果在2到i-1这个范围内被其中一个数整除了那么这个数字一定不是素数，也不用再进行后面的循环试除.
			}
		}
		if (j <= (int)sqrt(i))				//这个条件满足时，说明i在j <= (int)sqrt(i)范围内被整除了，不是素数.
		{
    					
			;		//空语句
		}
		else
		{
    
			printf("%d是素数\n", i);		//反之，如果j >(int)sqrt(i)也就是i没有在j <= (int)sqrt(i)范围内被整除了,这个数就是素数
		}
	}
	return 0;
}

运行结果：

*试除法(高级)

你暗自高兴留了一手，咔咔写出优化的代码交给面试官。面试官脸上有了点欣慰的笑容，随后又问道，还可以再优化一下吗？这时候一些好不容易写出优化代码的同学内心就有点崩溃了。别慌这个优化的代码也就是优化了一小处。

可以发现，大多数的素数都不能被2整除，那么不能被2整除可不可以排除质数一定不是偶数呢？这里告诉大家，除了2这个偶数是素数，其他偶数都不是素数。所以我们试除法的试除范围是不是又可以缩小了呢？也就是在判断一个数是不是素数的范围中可以每次从一个奇数开始即是一个奇数+2还是奇数，这里除了从1开始+2跳过了2这个也特殊的素数，如果要判断这个素数可以不用这种方法。那么判断100到200的素数，就可以从101这个奇数开始每次+2来跳过这个范围的偶数，来提升效率。

代码如下:

#include<stdio.h>
#include<math.h>
int main()
{
    
	int i = 0;
	for (i = 101; i <= 200; i+=2)		//跳过100-200之间的偶数
	{
    
		int j = 0;
		for (j = 2; j <= (int)sqrt(i); j++)
		{
    
			if (i % j == 0)
			{
    
				break;		//如果在2到i-1这个范围内被其中一个数整除了那么这个数字一定不是素数，也不用再进行后面的循环试除.
			}
		}
		if (j <= (int)sqrt(i))				//这个条件满足时，说明i在j <= (int)sqrt(i)范围内被整除了，不是素数.
		{
    					
			;		//空语句
		}
		else
		{
    
			printf("%d是素数\n", i);		//反之，如果j >(int)sqrt(i)也就是i没有在j <= (int)sqrt(i)范围内被整除了,这个数就是素数
		}
	}
	return 0;
}

运行结果：

这时候面试官才眉笑颜开道"小伙子，不错，有前途！"

*结言

看了这篇文章会怎么判断了吧，敬请期待后面的题目哦。我们下期见！