山东青岛网站建设,win7的iis怎么制作网站,百度关键词推广价格查询,自搭建网站一、朴素筛法#xff08;埃拉托斯特尼筛法#xff09;Eratosthenes 筛法#xff08;埃拉托斯特尼筛法#xff0c;简称埃氏筛法#xff09;时间复杂度是O(nloglogn)不常用#xff0c;被欧拉筛代替#xff0c;略二、线性筛素数#xff08;欧拉筛法#xff09;简介线性筛…一、朴素筛法埃拉托斯特尼筛法Eratosthenes 筛法埃拉托斯特尼筛法简称埃氏筛法时间复杂度是O(nloglogn)不常用被欧拉筛代替略二、线性筛素数欧拉筛法简介线性筛法 也称为 Euler 筛法欧拉筛法对比普通的筛法就是1到n的倍数来筛线性筛就是 用1到n中的素数的倍数来筛时间复杂度 O(n) buff筛法求素数的同时也得到了每个数的最小质因子。原理中心思想每个数只能被自己的最小质因子筛掉一次算法原理解释原理对于任意合数必定可以有最小质因子乘以最大因子的分解方式。因此对于每个合数只要用最大因子筛一遍枚举时只要枚举最小质因子即可。由于每个合数都只被标记一次达到了线性// 任意合数必定可以有最小质因子乘以最大因子的分解方式。// 所以我们只要保证每个合数都由最小质因子筛掉就行了//用两层循环枚举最小质因子和最大因子。i是最大因子prime[j]是最小质因子break整除中断原因解释1// 这里为什么要break// 因为如果不break// i * p[j 1] 的最小质因子就不是p[j 1] 了// 而是 i 的最小质因子 p[j]。解释2//这个break发生时这个primes[j]的值是i的最小质因子//保证合数只被最小质因子划掉一次 //如果i是质数则最多枚举到自身中断 //如果i是合数则最多枚举到自身的最小质数中断文章【算法/数论】欧拉筛法详解过程详述、正确性证明、复杂度证明_CSDN博客_欧拉筛例题P3383 【模板】线性筛素数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)Sherlock and his girlfriend - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)三、与回文数结合回文数判断回文数构造回文数回文质数偶数肯定不是质数。这样至少排除一半多的数据量知识点 “偶数长度的回文数”中只有11是素数其他的都可以被11整除。偶数位数回文数除11必定不是质数例题回文素数 - 回文素数 - 力扣LeetCodeP1217 [USACO1.5]回文质数 Prime Palindromes - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)四、与合数结合方法用欧拉筛反向筛出合数合数相关理论例题P1835 素数密度 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)模板/*prime_nums_Euler*/
#includebits/stdc.h
#define MAXN 100000005
using namespace std;//P3383 【模板】线性筛素数bool isprime[MAXN]; // isprime[i]表示i是不是素数
int prime[MAXN]; // 现在已经筛出的素数列表
int nums 0; // 已经筛出的素数个数void euler_old(int n){memset(isprime, true, sizeof(isprime)); // 先全部标记为素数isprime[1] false; // 1不是素数for(int i 2; i n; i){ // i从2循环到n外层循环if(isprime[i]) prime[nums] i;// 如果i没有被前面的数筛掉则i是素数for(int j 1; j nums prime[j] n/i; j){//枚举已经记录的质数内层循环//i * prime[j] n由于题目只求小于n的数是否是质数所以大于n的就不管了【越界中断】isprime[i * prime[j]] false;// 倍数标记为合数也就是i用prime[j]把i * prime[j]筛掉了if(i % prime[j] 0) break;//【整除中断】}}
}//以下是acwing的模板int primes[MAXN], cnt; // primes[]存储所有素数
bool st[MAXN]; // st[x]存储x是否被筛掉:true表示要被筛掉没有处理1的特判void get_primes(int n){for(int i 2; i n; i){if(!st[i]) primes[cnt] i; //如果没有被筛掉直接录入并且cntfor(int j 0; primes[j] n/i; j){ //从小到大枚举所有质数st[primes[j] * i] 1; //筛掉质数的倍数的数if (i % primes[j] 0) break; //【精髓整除中断】//这个break发生时这个primes[j]的值是i的最小质因子}}
}int main(){int n; // 上限即筛出n的素数scanf(%d, n);get_primes(n);int q,k;//q次询问第 k 小的素数scanf(%d, q);while(q--){scanf(%d, k);printf(%d\n, primes[k-1]);}// for(int i 2; in; i) if(isprime[i]) printf(%d , i);// for(int i 2; in; i) if(!st[i]) printf(%d , i);return 0;
}
