乌班图系统做网站,envato wordpress toolkit,写网站教程,河北邯郸区号算法之素数筛
素数筛
引言#xff1a;
素数(质数)#xff1a;除了1和自己本身之外#xff0c;没有任何因子的数叫做素数(质数)
朴素筛法(优化版)
概念#xff1a;
朴素筛法#xff1a;是直接暴力枚举2到当前判断的数x(不包括)#xff0c;然后看在这范围内是否存在因…算法之素数筛
素数筛
引言
素数(质数)除了1和自己本身之外没有任何因子的数叫做素数(质数)
朴素筛法(优化版)
概念
朴素筛法是直接暴力枚举2到当前判断的数x(不包括)然后看在这范围内是否存在因子如果存在就不是素数不存在就是素数时间复杂度为O(n*n)优化版优化版是用到了一个数学性质进行优化使其只需要判断2到sqrt(x)的范围内是否存在x的因子即可时间复杂度为O(n*sqrt(n))
数学性质如果一个数x能够被一个大于1且小于等于sqrt(x)的整数整除那么x必定能够被另一个大于1且大于sqrt(x)的整数整除。
#include iostream
using namespace std;//朴素筛素数判断算法时间复杂度O(n)
bool isprime1(int x){if(x1) return false;if(x2) return true;for(int i2;ix;i){if(x%i0) return false;}return true;
}//优化版素数判断算法时间复杂度O(sqrt(n))
bool isprime(int x){if(x1) return false;if(x2) return true;for(int i2;ix/i;i){if(x%i0) return false;}return true;
}int main() {//假设筛选出1-1000的素数for(int i1;i1000;i2){if(isprime(i)) coutiendl;}system(pause);return 0;
}欧拉筛(线性筛)
概念
欧拉筛利用合数的数学性质可以将素数筛的算法优化到时间复杂度为O(n)
合数除了1和自身之外还有其他正因子(除了 1 和自身以外的能够整除它的正整数)并且大于1的整数
数学性质对于任意一个合数 x它一定可以被其最小质因数(即最小的能整除 x 的质数)整除
算法具体操作
初始化一个标记数组vis[]和记录素数数组primevis所有元素初始化为false从2遍历到n(要筛选素数范围)如果vis[i]为false则将i标记为素数并将i记录在prime数组中并将i的倍数j(ji*ii*ii…)标记为合数(true)遍历完所有的数后prime数组中的数都为素数 总结 在这个过程中每个合数都会被标记为其最小质因数这样能够确保每个合数只会被标记一次。由于每个合数只会被其最小质因数标记因此在遍历过程中每个合数只会被标记一次而非多次从而避免了重复标记提高了效率。 const int N1e810;
int prime[N];
bool vis[N];//欧拉筛总体时间复杂度为O(n)
void isprimes(int n){int cnt0;for(int i2;in;i){if(!vis[i]) prime[cnt]i;for(int j0;prime[j]n/i;j){vis[i*prime[j]]true;if(i%prime[j]0) break;}}
}尾言
完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看或者在github库中自取(包含源代码) 博客1 codebooks.xyz博客2moonfordream.github.iogithub项目地址Data-Structure-and-Algorithms
