【C语言】求质数（常规法与平方根法）_寻找素数平方根法cyuyan

【C语言】求100~200之间的质数（常规法与平方根法）

质数定义

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。
根据定义可以看出：一个数如果可以被除了1或它本身以外的正整数整除，那么它就不是质数。

常规法

思路

我们从以上定义可以得知，质数只有两个因数：1和它本身。
假设有一个数n，若是在2~n-1范围内存在一个整数，可以将n整除，那么n就是非质数。

代码

#include <stdio.h>
int is_prime(int i)
{
	int j = 0;
	for (j = 2; j <= i - 1; j++)
	{
		if (i % j == 0)         //i能被j整除，所以i不是质数，返回0，不打印
		{
			return 0;
		}

	return 1;                  //i不能被j整除，是质数，返回1，打印
}

}
int main()
{
	int i = 0;
	for (i = 101; i <= 199; i += 2)      //除了2，所有偶数都是非质数，所以在此排除偶数
	{
		if (is_prime(i))                 //函数判断，若i是质数就返回1，打印i
			printf("%d ", i);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

运行结果

平方根法（sqrt）

思路

假设数m是一个非质数，那么m就可以写为这种形式：m = a * b 和 m = i * i
a和b其中一个是必定小于i的。

常规法中，我们遍历的是2~m-1这个范围。
而在平方根法中，我们只需遍历2~sqrt(m)这个范围，极大提高了代码运行效率。

代码

#include <stdio.h>
#include <math.h>      //函数sqrt()的头文件
int is_prime(int i)
{
	int j = 0;
	for (j = 2; j <= sqrt(i); j++)   //求一个数的开平方，需用函数sqrt()
	{
		if (i % j == 0)         //i能被j整除，所以i不是质数，返回0，不打印
		{
			return 0;
		}

return 1;                  //i不能被j整除，是质数，返回1，打印

}

}
int main()
{
	int i = 0;
	for (i = 101; i <= 199; i += 2)      //除了2，所有偶数都是非质数，所以在此排除偶数
	{
		if (is_prime(i))                 //函数判断，若i是质数就返回1，打印i
			printf("%d ", i);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

运行结果

总结

质数的因数只有1和它本身
除去2，偶数都不是质数
设非质数m，在范围2~sqrt(m) 中必定存在一个数可以将m整除