Ealin

用户名：Ealin

访问量：16067

签　名：

宝剑锋从磨砺出，梅花香自苦寒来。

等　　级
排　　名	71
经　　验	10249
参赛次数	1
文章发表	33
年　　龄	0
在职情况	待业
学　　校	无
专　　业

　　自我简介：

TA的其他文章

小O的质数-题解(C++代码)
浏览：486

蓝桥杯算法提高VIP-计算器-题解(C++代码)
浏览：282

蓝桥杯算法提高VIP-进制转换-题解(C语言代码)
浏览：790

你可能喜欢

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

素数素数素数素数素数素数素数素数素数素数素数

　　作者: Ealin　　　　发表时间：2019-07-02 01:57:02 浏览：986　|　评论：0　

#素数
> 
####本文以**“求小于等于n的素数之和”**这个题目为引，讲一下求素数几种方法的思想。

[========]
###1. 试除法
> **思路：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数(素数)。那么我只需要将自然数循环从2判断到它本身，如果没有被其他自然数整除，那么这个就是素数。**

```cpp
int sumOfPrime1(int n)
{
	int sum = 0;
	for (int i = 2; i <= n; ++i){
		int j = 2;
		for (; j < i; ++j)
		{
			if (i%j == 0)
				break;
		}
		if (j >= i)
			sum += i;
	}
	return sum;
}
```
[========]
###2. 试除法(sqrt版本)
> **思路：在试除法的基础上优化。假设num为合数，因为任何一个合数都可以分解成两个整数的乘积，即num=x*y，因为x和y都大于sqrt(num)是不成立的，所以x和y中一定有一个是小于等于sqrt(num)，这样我们就得出一个理论：一个大于1的自然数num，从2到sqrt(num)中，不能被其他自然数整除的数叫做质数(素数)。**

```cpp
int sumOfPrime2(int n)
{
	int sum = 0;
	for (int i = 2; i <= n; ++i){
		int j = 2;
		for (; j <= sqrt(i); ++j)
		{
			if (i%j == 0)
				break;
		}
		if (j > sqrt(i))
			sum += i;
	}
	return sum;
}
```
[========]
###3. 试除法(sqrt优化版本)
> **思路：在暴力法(sqrt版本)的基础上优化。因为比2大的偶数都是2的倍数，即合数，所以，除了2以外，所有的质数都是奇数,这样我们就可以直接把所有偶数忽略掉啦。**

```cpp
int sumOfPrime3(int n)
{
	int sum = 0;
	if (n > 1)
		sum = 2;
	for (int i = 3; i <= n; i += 2){
		int j = 3;
		for (; j <= sqrt(i); j += 2)
		{
			if (i%j == 0)
				break;
		}
		if (j > sqrt(i))
			sum += i;
	}
	return sum;
}
```
[========]
###4. 埃氏筛法
> **思路：因为任意一个合数至少有一个质因数，所以从2开始，把所有素数的倍数标记起来，那么剩下的没有标记的就是素数。
简单模拟一下：
假设n=20
i=2 标记：4，6，8，10，12，14，16，18，20
i=3 标记：9，12，15，18
i=4 不处理（已经在i=2的时候标记为合数了）
i=5 i>sqrt(n)跳出循环
所以小于等于n的素数之和为2+3+5+7+11+13+17+19=77
**

```cpp
int sumOfPrime4(int n)
{
	bool *isprime = new bool[n + 1]{};
	for (int i = 2; i <= sqrt(n); ++i)
	{
		if (isprime[i] == false){
			for (int j = i * i; j <= n; j += i)
			{
				isprime[j] = true;
			}
		}
	}
	int sum = 0;
	for (int i = 2; i <= n; ++i)
	{
		if (isprime[i] == false)
			sum += i;
	}
	delete[] isprime;
	return sum;
}
```
[========]
###5. 埃氏筛法(优化版本)
> **思路：在埃氏筛法的基础上，避免偶数的标记。
简单模拟一下：
假设n=20 
i=3 标记：9，15，
i=5 i>sqrt(n)跳出循环
所以小于等于n的素数之和为3+5+7+11+13+17+19=75+2=77
**

```cpp
int sumOfPrime5(int n)
{
	bool *isprime = new bool[n + 1]{};
	for (int i = 3; i <= sqrt(n); i += 2)
	{
		if (isprime[i] == false){
			for (int j = i * i; j <= n; j += i * 2)
			{
				isprime[j] = true;
			}
		}
	}
	int sum = 0;
	if (n > 1)
		sum = 2;
	for (int i = 3; i <= n; i += 2)
	{
		if (isprime[i] == false)
			sum += i;
	}
	delete[] isprime;
	return sum;
}
```
[========]
###6. 欧拉筛法
> **把所有质数的倍数标记起来且只标记一次，那么剩下的没有标记的就是素数。
欧拉筛法和埃氏筛法的唯一区别就是：埃氏筛法在标记合数的时候，会有重复标记的情况，而欧拉筛法，在标记合数的时候，每次都使用最小的质因数去标记，避免了重复标记的情况，所以更快。**

>**简单模拟一下：（因数即为i，质因数为prime[j]）
假设n=20
因数为2，质因数为2，标记合数4
因数为3，质因数为2，标记合数6;质因数为3，标记合数9
因数为4，质因数为2，标记合数8；4%2==0跳出内层循环
因数为5，质因数为2，标记合数10；质因数为3，标记合数15；质因数为5，5x5>n跳出内层循环
因数为6，质因数为2，标记合数12；6%2==0跳出内层循环
因数为7，质因数为2，标记合数14；质因数为3，7x3>n跳出内层循环
因数为8，质因数为2，标记合数16；8%2==0跳出内层循环
因数为9，质因数为2，标记合数18；质因数为3，9x3>n跳出内层循环
因数为10，质因数为2，标记合数20；质因数为3，10x3>n跳出内层循环
因数为11，质因数为2，11x2>n跳出内层循环
因数为12，质因数为2，12x2>n跳出内层循环
因数为13，质因数为2，13x2>n跳出内层循环
因数为14，质因数为2，14x2>n跳出内层循环
因数为15，质因数为2，15x2>n跳出内层循环
因数为16，质因数为2，16x2>n跳出内层循环
因数为17，质因数为2，17x2>n跳出内层循环
因数为18，质因数为2，18x2>n跳出内层循环
因数为19，质因数为2，19x2>n跳出内层循环
因数为20，质因数为2，20x2>n跳出内层循环
因数为21，21>n跳出外层循环
所以小于等于n的素数之和为2+3+5+7+11+13+17+19=77
**

```cpp
int sumOfPrime6(int n)
{
	int sum = 0;
	int count = 0;
	int *prime = new int[n + 1]{};
	bool *isprime = new bool[n + 1]{};
	for (int i = 2; i <= n; ++i)
	{
		if (isprime[i] == false){//保存质数
			sum += i;
			prime[count++] = i;
		}
		for (int j = 0; j < count&&i*prime[j] <= n; ++j)
		{
			isprime[i*prime[j]] = true;
			if (i%prime[j] == 0)//这句的作用就是要确定prime[j]是最小的质因数
				break;
		}
	}
	delete[] prime;
	delete[] isprime;
	return sum;
}
```
[========]
###7. 欧拉筛法(优化版本)
> **思路：在欧拉筛法的基础上，避免偶数的判断。**
**

```cpp
int sumOfPrime7(int n)
{
	int sum = 0;
	int count = 0;
	int *prime = new int[n + 1]{};
	bool *isprime = new bool[n + 1]{};
	if (n > 1){
		prime[count++] = 2;
		sum = 2;
	}
	for (int i = 3; i <= n; i += 2)
	{
		if (isprime[i] == false){
			sum += i;
			prime[count++] = i;
		}
		for (int j = 1; j < count&&i*prime[j] <= n; ++j)
		{
			isprime[i*prime[j]] = true;
			if (i%prime[j] == 0)
				break;
		}
	}
	delete[] prime;
	delete[] isprime;
	return sum;
}
```

[========]

> ####对于两种筛法空间的优化：可以用1位来标记1个合数，合数为1，素数为0，这样一个字节可以标记8个数字，相比使用bool类型来标记可以节省8倍的内存空间。
定义位域
struct S_Prime{
unsigned int a:1;
};
S_Prime prime[100];

#如有不同的见解，可以在评论区留言，一起探讨，共同进步。

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Ealin

TA的其他文章

你可能喜欢

C二级辅导-计负均正（C++代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

素数素数素数素数素数素数素数素数素数素数素数

评论区

精彩推荐

1908题解

关于C语言变量位置的问题

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

字符逆序（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

简单的a+b （C语言代码）

Ealin

TA的其他文章

你可能喜欢

C二级辅导-计负均正 （C++代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

素数素数素数素数素数素数素数素数素数素数素数

评论区

精彩推荐

1908题解

关于C语言变量位置的问题

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

字符逆序 （C语言代码）

青年歌手大奖赛_评委会打分 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-计负均正（C++代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

　　评论区

字符逆序（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）