也许，所有的程序员学习数学编程时遇到的问题之一是检查一些材料必须是一个 灌注 或不.

第一种算法对我们说: 检查的数量很可能是n的除数 (需要检查的元素), 这些数字，从 2 到n – 1. 该算法安装在C简单地如下:

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i < n; i++)
		if (n % i == 0)
			return 0;
	return 1;
}

安装上, 如果n是素数，则循环运行，直到我= N – 1 要能够使最终的结论. 然而, 想多一点，我们会看到，不需要检查值i = N – 1 其基本上只是到n / 2 (ñDIV 2) 因为没有n时的除数大于n / 2的. 因此，算法如下:

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i <= n / 2; i++)
		if (n % i == 0)
			return 0;
	return 1;
}

回想一点点，我们会看到，也没有必要检查值n / 2只需要根 2 n为 (你算算看，看看为什么这么 ). 我们有新算法: (注声明库 文件math.h 计算基)

#include <math.h>

int checkPrime(int n) {
	if (n < 2)
		return 0;
	int i;
	for (i = 2; i <= sqrt(n); i++)
		if (n % i == 0)
			return 0;
	return 1;
}

素数也可能只是除了数奇数 2, 因此，它们不能被分配给偶数，所以我们只需要检查除数 (我的价值) 是奇数, 所以接下来的算法如下:

#include <math.h>
int checkPrime(int n) {
	int i;
	int m;
	if (n < 2)
		return 0;
	if (n == 2)
		return 1;
	if (n % 2 == 0)
		return 0;

	m = (int) sqrt(n);
	for (i = 3; i <= m; i += 2)
		if (n % i == 0)
			return 0;
	return 1;
}

比以前的算法清除, 我的价值应该检查减半. 因此，要加速和改进算法在于在声明中键来改变控制变量i的值, 我们只需要减少的价值，我应该检查将导致更有效的算法.
最近，我们通过考虑除数消除我的价值的一半 2 可能的n. 下一步，我们将考虑未来估计质数可能的n提高算法是多少 3. 如果n整除 2 或 3 然后轻松地断定它是一些 (当然，其它的两个值的N必须). 相反地​​Ñ将具有形式1 + 6I近似数,5+6在 , 我将开始与i的值= 5. 但是，如果在1个+ 6I的形式，只有我会缺少测试的候选人，所以我们将检查i的值+ 2个 (注意: 当我们开始以i = 5那么我们有I + 2 <=> 1 + 6) 足够. 因此，新算法 (5) 将如下:

#include <math.h>
int checkPrime(int n) {
	int i;
	int m;

	if (n < 2)
		return 0;

	if (n == 2 || n == 3)
		return 1;
	if (n % 2 == 0 || n % 3 == 0)
		return 0;
	
	m = (int) sqrt(n);
	for (i = 5; i <= m; i = i + 6)
		if (n % i == 0 || n % (i + 2) == 0)
			return 0;
	return 1;
}

在审查反复素数是通过使用技术算法也可以改善这个问题 筛元素 这里.

通过简单的算法演示，检查小素数, 我希望给你一个很好的算法编程竞赛或问题，使用中的小, 并且由此示出的设置调整的算法. 可以在相同的算法，但使用不同的设置, 效果会有所不同, 和更有效时，是基于细节似乎很小资, 不显着.

如果有什么好的算法, 有, 我们正在寻找的成就我们共同讨论, 了解更多.

原创文章 / 资源: vietsource.net