可算把「素数」玩明白了
🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 关注专栏：关注🥇 大学算法成神路 🥇专栏不迷路，优质好文持续更新中……🚀
目录
在算法的学习过程中，素数问题一直是一个热点，关于素数的题目非常多。本篇文章就来讲解下素数以及如何求解素数。
猿哥一直秉承知其然知其所以然的态度分享知识，下面先来看一下素数的定义。
🍓一、什么是素数
素数是指在大于 1 的自然数中，除了 1 和本身外无法被其它自然数整除的数，即：只有 1 和 本身两个正因数，也被称为质数。
例如：10 以内的素数包括 {2，3，5，7}，它们都只能被 1 和 本身整除。
现在明白了什么是素数，下面就来判断一个数是不是素数。
-
// 100 以内的素数
-
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
🔶🔶🔶 我是华丽的分割线 🔶🔶🔶
🍓二、判断素数
判断素数的方法有很多，下面来介绍三种常见的方法，一种是根据定义判断一个数是否是素数，另一种是开方的方法，还有一种是线性筛法。
🚩2.1 定义法
假设判断 n 是否是素数，定义法是依次判断从 2 ~ n-1 是否可以整除 n。如果存在可以整除的数，则 n 为合数，否则为素数，是不是和定义一样呀！
代码如下所示。
-
bool isPrime(int n) {
-
if(n <= 3) // 简化操作
-
return true;
-
for(int i = 2; i < n; ++i) {
-
if(n % i == 0) // 判断 i 是否可以整除 n
-
return false;
-
}
-
return true;
-
}
🚩2.2 开方法
如果 n 是合数，必定存在一对因子 q1 和 q2，且满足条件 q1 <= sqrt(n)，q2 >= sqrt(n) , q1 * q2 = n。那么，只需要找到 q1 即可证明是合数，所以判断范围缩小为 2 ~ sqrt(n)。
例如：求解 10 是否是素数，10 的因子有 2，5，求解 2 ~ sqrt(10) 的整数是否可以整除 10 即可，因为 2 在此范围内。
代码如下所示。
-
bool isPrime(int n) {
-
if(n <= 3) // 简化操作，并处理特殊情况 2
-
return true;
-
for(int i = 2; i <= sqrt(n); ++i) { // sqrt为开方函数
-
if(n % i == 0)
-
return false;
-
}
-
return true;
-
}
🚩2.3 线性筛法求素数
线性筛法原理：每一个合数只被最小素因子筛选一次。
线性筛法通过每个合数自身的最小质因子来筛出合数，每个合数只筛选一次，因为一个合数一定可以分解为一个素数与另一个数的乘积，标记合数时用那个合数最小的素因子标记。
例如：标记 30 用 2 * 15 标记，而不用 3 * 10 去标记。
-
#include <iostream>
-
#include <cmath>
-
#include <cstdlib>
-
#include <cstring>
-
using namespace std;
-
-
const int MAX_LEN = 1000;
-
int num = 0;
-
int prime[MAX_LEN];
-
bool isPrime[MAX_LEN];
-
/*
-
* 线性筛法,
-
*/
-
bool judgePrime(int n) {
-
memset(isPrime, false, sizeof(isPrime));
-
for(int i = 2; i <= n; ++i) {
-
if(!isPrime[i])
-
prime[num++] = i ;
-
for(int j = 0; (j < num && i * prime[j] <= n); ++j) {
-
isPrime[i * prime[j]] = true ;
-
if(!(i%prime[j]))
-
break ;
-
}
-
}
-
}
-
-
int main()
-
{
-
judgePrime(100);
-
for(int i = 0; i < num; ++i) {
-
cout<<prime[i]<<" ";
-
}
-
cout<<endl;
-
return 0;
-
}
在上述三种方法中，方法 1 因复杂度为 O(n)，一般不用。方法 2 通常用来判断单个数是否是素数 。方法 3 通常用于筛出一个区间里的素数。
🔶🔶🔶 我是华丽的分割线 🔶🔶🔶
🍓三、实战演练
掌握了上面的方法后赶紧来实践下吧！
[1] http://poj.org/problem?id=2262
🔶🔶🔶 我是华丽的分割线 🔶🔶🔶
🍓四、总结
本文主要对素数的求解方法进行了讲解，主要掌握单个素数以及区间素数的求解方法，可以根据实战演练里的两个题目进一步加深理解。
🎈 整理不易，感觉有帮助记得「一键三连」支持下哦！有问题可在评论区留言💬，感谢大家的一路支持！🤞猿哥将持续输出「优质文章」回馈大家！🤞🌹🌹🌹🌹🌹🌹🤞
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/122391284
- 点赞
- 收藏
- 关注作者
评论（0）