[C++知识库]C语言判断素数方法之试除法

?素数又称质数，指的是一个大于1的正整数，如果除了1和它本身以外，不能被其他正整数整除，就叫素数，如2，3，5，7，11，13，17…。接下来让我们以打印区间【a，b】内所有素数为目标来探究一种判断素数最简单的方法：试除法。

那么首先让我们生成a到b间的所有数，记为i，用一个简单的for循环就能解决，接下来我们要判断生成的数是不是素数，我们可以从素数最简单的性质出发：除了1和它本身以外，不能被其他正整数整除，（我们当然只需要考虑小于这个数的正整数）那么让我们生成从2到i-1的所有数，记为c也是一个for循环就能解决，然后让i去模上每一个c，只要出现一个i%c为0，c就不必继续生成了，直接跳出内循环，内循环结束，而当所有c都不使循环break，内循环也会结束，此时的i就是素数了，但是两种情况内循环都会结束，我们怎么区别出哪种情况i为素数呢，我们注意到内循环正常结束时c的值于i相等，那么我们在内循环后面加上一个if判断，剔除掉break出的i，只选择正常结束的i，并将其打印，计数器加一

#include <stdio.h>
int main()
{
	int a=0;
	int b=0;
	int i=0;
	int c = 0;
	int num = 0;
	scanf("%d%d", &a, &b);
	for (i = a; i <= b; i++)
	{
		for (c = 2; c <= i - 1; c++)
		{
			if (i%c == 0)
			{
				break;
			}
		}
		if (c == i)
		{
			printf("%d ", i);
			num++;
		}
	}
	printf("\n有%d个素数", num);
	return 0;
}

?上面的思路没问题，但是略显繁琐，我们可以利用素数的一个性质来优化该代码，我们发现，其实一个数字x的因数分成两大部分，一部分是小于x的平方根，另外一部分大于x的平方根，小于平方根和大于平方根的部分是一一对应的，例如24=2*12=3*8=4*6，只要在2到x的二次方根内找到一个能整除x的数就能判定x不是素数。我们要用根号函数sqrt（）需要引用头文件<math.h>，修改后得到以下代码

#include <stdio.h>
#include <math.h>
int main()
{
	int a = 0;
	int b = 0;
	int i = 0;
	int c = 0;
	int num = 0;
	scanf("%d%d", &a, &b);
	for (i = a; i <= b; i++)
	{
		for (c = 2; c <= sqrt(i*1.0); c++)
		{
			if (i%c == 0)
			{
				break;//跳出内循环
			}
		}
		if (c > sqrt(i*1.0))
		{
			printf("%d ", i);
			num++;
		}
	}
	printf("\n总共有%d个素数", num);
	return 0;
}

问题便得到解决了。