求素数的三大算法 —— C 语言 篇_素数算法

求素数的三大算法 —— C 语言 篇

---

• 素数又叫质数（prime number），有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

---

算法一 ：暴力遍历

思路：

1. 素数我们运用两个循环的遍历的方式，首先根据素数的定义：质数定义为在大于1的自然数中，除了1和它本身以外不再被其数整除了。因为任何数都可以被 1 整除的，所以我们的第一个for( )循环语句的初始值从 2 开始进行，到你所需的范围。
2. 我们的第二个for（）循环语句，的判断条件是：从上个for（）循环语句的 变化值开始，但是注意不要等于 因为不要除以它本身，其中我们 if（） 语句判断是否有，被除了它本身以外的数整除，同时我们定义一个变量，用于标记该数是否为被整除，逆向思考，被整除了，就不是素数，否则为素数
3. 最后我们通过我们的标记，判断素数需要打印数值，
4. 查找的时间复杂度为 O(n)

---

代码：

// 暴力遍历法
int main()
{
	int n = 0;
	int count = 0;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++)
	{
		int sign = 1;
		for (int j = 2; j < i; j++)
		{
			if (i % j == 0) {
				sign = 0;
				break;
			}
		}
		if (sign == 1)
		{
			printf("%d ", i);
			count++;
			if (count % 5 == 0)
			{
				printf("\n");
			}

		}
		

	}

	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
28
29
30
31
32
33
34

---

算法二：折半范围遍历

思路：

• 在第一个算法的基础上，改进之法
• 请看下图所示：

• 我们仔细观察上述的图解：发现其规律没有：
  • 所有的数的可以被整除的最大的，除数都是 {其数值的 / 2 的 }如：18 的可以被最大的整除的是 (18/2 =) 9 , 12 可以被最大的整除的数是 (12 /2 =) 6 ;
  • 所以我们只要判断其数值的 1/2的范围内 是否有被整除 (除 1 外) 就可以了，会被整除就不是素数，不会整除就是素数
• 逆向思考，这样我们就缩小了遍历范围，在第一种算法的基础上减半，
• 查找的时间复杂度为 O(n/2)

---

代码：

#include<
// 折半范围遍历
int main()
{
	int n = 0;
	scanf("%d", &n);
	int count = 0;
	for (int i = 2; i <= n; i++)
	{
		int sign = 1;
		for (int j = 2; j <= i / 2; j++)
		{
			if (i % j == 0)
			{
				sign = 0;
				break;
			}

		 }

		if (sign == 1)
		{
			printf("%d\t", i);
			count++;
			if (count % 5 == 0)
			{
				printf("\n");
			}
		}
	}

	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
28
29
30
31
32
33

---

算法三：根号范围遍历

思路：

• 同样是在第一个算法的基础上改进的

• 请看下面的图示：

  • 

• 仔细观察图示，有没有发现，我们求他们的平方根看看，结果：

• 发现在它们的平方范围内，都会有可以被整除的数值，（当然我们这里不是素数的数值）逆向思考：不是的不就是素数了吗？

• 这样我们再次缩小了遍历的范围了，在第一种算法的基础上减了，一个根号范围；

• 查找的时间复杂度为 O(根号n )

---

代码：

#include<stdio.h>
#include<math.h>
// 根号范围遍历
int main()
{
	int n = 0;
	int count = 0;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++)
	{
		int sign = 1;
		for (int j = 2; j <= (int)sqrt(i); j++) // sqrt 求平方根的函数，返回                                                             // 值是 double ,所以这里强转一下
		{
			if (i % j == 0)
			{
				sign = 0;
				break;
			}
		}
		if (sign == 1)
		{
			printf("%d\t", i);
			count++;
			if (count % 5 == 0)
			{
				printf("\n");
			}
		}
	}


	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
28
29
30
31
32
33

---

总结：

• 总的来说通过找寻到某种规律：从而缩小查找的范围：如第一种算法：中我们查找的范围是 n , 第二种算法中：我们查找的范围是 n / 2 ，第三中算法：我们的查找范围是 根号 n
• 从而达到实现提高程序的效率

---

最后：

每博一文案

与其把时间花在争论上，不如多花些点时间提高自己？

让那些不懂你的人望尘莫及，有些话不说，有些事不争人生就是个不断成熟的过程。

等你真正得到境界的提升，你就会发现，与你志同道合的人越来越多，不说不争，也能找到中窝

​ ———— 一禅心灵庙语

限于自身水平有限，其中存在的错误希望大家给予指教，谢谢大家，韩信点兵——多多益善！，后会有期，江湖再见！