-
2021-05-22 08:41:14
第一种:开根号,这里不再重述
第二种:Eratosthenes筛选法
原理:利用倍数,讲非素数筛选掉
code:
1 int vis[maxn];
2 void Prime()
3 {
4 vis[0] = 1;
5 vis[1] = 1;
6 for(int i = 2; i <= maxn; i++) //任何数的倍数都标记为1证明其不是素数
7 {
8 if(!vis[i])
9 {
10 for(int j = i*2; j <= maxn; j += i)
11 {
12 vis[j] = 1;
13 }
14 }
15 }
16 }
第二种:欧拉筛法
原理:每个合数都会被它的最小因子筛掉,而我们的最小因子即记录在 Prime 数组(就是拿已经筛选出来的素数乘当前的数i,结果即为合数,筛掉),详细看代码注释
code:
1 bool vis[100001]={1,1};//0,1均既不是素数,也不是和数,所以先标记为不是
2 int Prime[100001],k;
3 void prime(long long num)
4 {
5 for(int i=2;i<=n;i++)//最小的素数是2
6 {
7 if(!vis[i])
8 {
9 Prime[++k]=i;//如果是素数就标记一下
10 }
11 for(int j=1;j<=k;j++)//j小于当前所有的素数的个数
12 {
13 if(Prime[j]*i>num)//如果已经大于最大的范围也没必要再往后筛选了
14 {
15 break;
16 }
17 vis[Prime[j]*i]=true;//用素数依次×i,结果标记为合数
18 if(i%Prime[j]==0) //每个数被它的最小因子晒掉 筛掉就break即可
19 {
20 break;
21 }
22 }
23 }//欧拉筛法,就是拿当前的数×之前的筛出来的素数,这个数即为合数
24 }
标签:Prime,int,质数,合数,vis,素数,筛选,Eratosthenes
来源: https://www.cnblogs.com/ZhengLijie/p/13121136.html
更多相关内容 -
20201211c欧拉筛选素数法1
2020-12-11 22:48:16首先,得需要知道什么是“素数”。...//欧拉筛选素数法 #include <stdio.h> int ys[2500001]={0};//值为0表示是素数 int main() { int i,j,a,b,max=0,t; for(i=2;i<=2500000;i++) { if(ys[i首先,得需要知道什么是“素数”。素数也是质数,根据百度所说:
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
而欧拉筛选则用到数组和两个for循环(应该吧,我也在学习中,所以标题有个“1”)//欧拉筛选素数法 #include <stdio.h> int ys[2500001]={0};//值为0表示是素数 int main() { int i,j,a,b,max=0,t; for(i=2;i<=2500000;i++) { if(ys[i]==0)//i的素数状态为0,表示i为素数 for(j=i+i;j<=2500000;j=j+i)//j的变化范围所有i的倍数,也就是说i是j的约数 ys[j]=1;//将j的素数状态置为1,表是j不是素数 } for(i=2;i<=1000;i++) if(ys[i]==0) { printf("%d,",i); } return 0; }
这是我们老师上课给我们展示的代码,大概的思路是:
设定一个等于0的数组,0代表为素数,代码中的2和2500000可以自己输入修改,
写第一个for循环,目的是将数据内所有包含的数都拿出来一遍,
如果数组内为0就继续,如果为一就直接跳过
第二个循环,让j等于两倍i,并且每次循环加上一个i(据说原本应该是乘的,但乘的话太容易越界了)每一次循环就让这个数对应的数组内等于1,因为j始终是i的倍数,所以j始终不是素数。
这样很快所有非素数的数组内就为1了
接下来只需要输出数组为0的就可以了。 -
素数筛选法和欧拉筛选法
2021-02-01 22:35:041、素数筛选法(时间复杂度O(nloglogN) /* 素数判断:素数筛选法(用素数筛选合数) */ #include <stdio.h> #include <math.h> #define MAX_N 100 //素数筛选法 int prime[MAX_N + 5] = {0};//初始...1、素数筛选法(时间复杂度O(nloglogN)
/* 素数判断:素数筛选法(用素数筛选合数) */ #include <stdio.h> #include <math.h> #define MAX_N 100 //素数筛选法 int prime[MAX_N + 5] = {0};//初始化为0 void init() { //素数筛选法 for(int i=2;i<=MAX_N;i++) { if(!prime[i]) {//素数时 prime[++prime[0]] = i;//prime[0]记录素数的个数,后面的依次储存素数 for(int j=i*i;j<=MAX_N;j+=i) { //此素数的倍数必为合数(可以不必从2*i开始筛) prime[j] = 1;//筛去 } } } } int main() { init(); printf("prime[0]:%d\n",prime[0]); for(int i=1;i<=prime[0];i++) { printf("%d ",prime[i]); } printf("\n"); return 0; }
2、应用:求1~n中每个数的最小素因子
/* 求2~n内每个数的最小素因子 */ #include <stdio.h> #include <math.h> #define MAX_N 100 int prime[MAX_N + 5] = {0};//初始化为0 void init() { for(int i=2;i<=MAX_N;i++) { if(!prime[i]) { prime[i] = i; //素数的最小素因子为她本身 for(int j=2*i;j<=MAX_N;j+=i) {//可以令j从i开始循环,这样可以省略上面那句话 if(!prime[j]) prime[j] = i; } } } } int main() { init(); for(int i=2;i<MAX_N;i++) { printf("MIN_factory[%d] = %d\n",i,prime[i]); } return 0; }
3、线性筛选(欧拉筛选,时间复杂度O(n))
/* 素数判断:线性筛选 */ #include <stdio.h> #include <math.h> #define MAX_N 100 //线性筛选(欧拉筛选) int prime[MAX_N + 5] = {0};//初始化为0 void init() { for(int i=2;i<=MAX_N;i++) { if(!prime[i]) { prime[++prime[0]] = i; //prime[0]记录素数的个数,后面依次储存素数(从prime[1]开始 } for(int j=1;j<=prime[0];j++) { if(i*prime[j] > MAX_N) break;//只需标记MAX_N以内的素数 prime[i*prime[j]] = 1; if(i%prime[j] == 0) break;//关键步骤,避免重复筛选 } } } int main() { init(); for(int i=1;i<=prime[0];i++) { printf("%d ",prime[i]); } printf("\n"); return 0; }
4、应用,求第10001个素数
/* 求第10001个素数 */ #include <stdio.h> #include <math.h> #define MAX_N 200000 //线性筛选(欧拉筛选) int prime[MAX_N + 5] = {0};//初始化为0 void init() { for(int i=2;i<=MAX_N;i++) { if(!prime[i]) { prime[++prime[0]] = i; //prime[0]记录素数的个数,后面依次储存素数(从prime[1]开始 } for(int j=1;j<=prime[0];j++) { if(i*prime[j] > MAX_N) break;//只需标记MAX_N以内的素数 prime[i*prime[j]] = 1; if(i%prime[j] == 0) break;//关键步骤,避免重复筛选 } } } int main() { init(); printf("%d\n",prime[10001]); return 0; }
答案是:104743
5、应用,求2~N内每个数的质因数个数
/* 求2~N内每个素的质因数个数,如2的质因数个数为2(1,2),4的质因数个数为3(1,2,4) */ #include <iostream> #include <stdio.h> using namespace std; #define MAX_N 100 int prime[MAX_N+5] = {0}; int factory_cnt[MAX_N] = {0}; void init() { //前半部分是线性筛选,后半部分是质因数分解定理 for(int i=2;i<=MAX_N;i++) { if(!prime[i]) prime[++prime[0]] = i; for(int j=1;j<prime[0];j++) { if(i*prime[j] > MAX_N) break; prime[i*prime[j]] = 1; if(i%prime[j]==0) break; } int tem = i; int j = 1; int cnt ,ans = 1; while(tem!=1) { cnt = 0; while(tem%prime[j]==0) { cnt++; tem /= prime[j]; } ans *= (1+cnt); j++; } factory_cnt[i] = ans; } } int main() { init(); for(int i=2;i<=MAX_N;i++) { printf("%d ",factory_cnt[i]); } printf("\n"); }
输出
2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6 4 4 2 8 3 4 4 6 2 8 2 6 4 4 4 9 2 4 4 8 2 8 2 6 6 4 2 10 3 6 4 6 2 8 4 8 4 4 2 12 2 4 6 7 4 8 2 6 4 8 2 12 2 4 6 6 4 8 2 10 5 4 2 12 4 4 4 8 2 12 4 6 4 4 4 12 2 6 6 9
更好的解法
#include <iostream> #include <memory.h> using namespace std; int main() { int m,n; cin>>m>>n; int * prime = new int[n+1]; int *cnt = new int[n+1]; int *fac = new int[n+1]; memset(prime,0,sizeof(int)*(n+1)); memset(cnt,0,sizeof(int)*(n+1));//储存最小因子的个数 memset(fac,0,sizeof(int)*(n+1));//储存因子个数 for(int i=2;i<=n;i++) { if(!prime[i]) { prime[++prime[0]] = i; fac[i] = 2; cnt[i] = 1; } for(int j=1;j<=prime[0];j++) { if(i*prime[j] > n) break; prime[i*prime[j]] = 1; if(i%prime[j]==0) { fac[i*prime[j]] = fac[i]/(cnt[i]+1)*(cnt[i]+2); cnt[i*prime[j]] = cnt[i] + 1; break; }else { fac[i*prime[j]] = fac[i]*fac[prime[j]]; cnt[i*prime[j]] = 1; } } } for(int i=m;i<=n;i++) { cout<<fac[i]<<"\n"; } delete[] prime; delete[] cnt; delete[] fac; }
-
欧拉筛素数法(简单易懂适合数学好的
2021-02-12 21:38:40素数(也称质数):只有1和它本身两个因数的自然数 合数:合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数 欧拉筛法的精髓就在于每个合数只筛了一次 (所以时间复杂度接近于O(n) 给出...既然你点进来,那一定让你懂的出去
概念
素数(也称质数):只有1和它本身两个因数的自然数
合数:合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数
欧拉筛法的精髓就在于每个合数只筛了一次
(所以时间复杂度接近于O(n)给出一个式子(相信您在其他地方已经看到过,或看到过类似的
这个式子非常重要
“最小质因数 × 最大因数(非这个合数) = 这个合数”先看一下板子
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxx=100000000+10; int s[6000000+10];//存素数 bool isprime[maxx];//如果是合数标记为1,是素数标0 int main(){ int n;//n为范围 std::ios::sync_with_stdio(0);//优化 cin>>n; int top=1; memset(isprime,1,sizeof(isprime)); isprime[1]=0; for(int i=2;i<=n;++i){ if(isprime[i]) s[top++]=i;// for(int j=1;j<=top && i*s[j]<=n/*i*s[j]不能超出求值得范围*/;++j){ isprime[i*s[j]]=0;//i*s[j]一定为合数 if(i%s[j]==0) break;//后面解释 } } for(int i=2;i<=top;++i) cout<<s[i]<<" "; return 0; }
其实核心代码就几行
for(int i=2;i<=n;++i){ if(isprime[i]) s[top++]=i; for(int j=1;j<=top && i*s[j]<=n;++j){ isprime[i*s[j]]=0; if(i%s[j]==0) break; } }
我们拆分出来一个一个理解
if(isprime[i]) s[top++]=i;
经过前i-2次的筛选(因为是从i=2开始筛,并且这个i还没有筛掉)后,这个i值还没有被筛掉,那它一定是素数
简单来说就是 此时i之前的 i和 s[j] 没有一个是当前这个数的因数
for(int j=1;j<=top && i*s[j]<=n;++j){
i*s[j]<=n的原因是保证筛选的合数在n的范围内
因为求的素数是<=n,所以也没必要再筛掉大于n的isprime[i*s[j]]=0; if(i%s[j]==0) break;
这两行合着一起讲
最小质因数 × 最大因数(非这个合数) = 这个合数
通过这个式子就能表示出一个合数i*s[j]=某个合数
s[j]是最小的质因数,i是最大因数
那么如何保证是s[j]是最小质因数了
这行代码的作用就来了if(i%s[j]==0) break;可谓是神来之笔
证明:
假设p=s[j]是合数c的最小质因数(s数组存放素数,且单调递增的当i%p== 0时,c== p* i==p* p *( i/p);
因为c是定值
如果这时p1=s[j+1]了
令d=i*p1,c!=d;//说明筛的不是同一个合数
而d=i*p1=s[j] * (i/s[j]) *p1
又因为s[j]<p1==s[j+1]
所以d的最小质因数应该是s[j]而不是s[j+1]
所以d的最大因数应该是 (i/s[j]) * p1
又因为 (i/s[j]) * p1>i
所以不在当前i%s[j]==0时停止,就会使后面的某个i*s[j]重复筛
而欧拉筛的要求就在于不能重复筛综上所以需要到i%s[j]== 0时,枚举下一个最小质因数为s[j+1]的数
(数学反证法)附赠一道练习题
有什么疑惑意见可以发出来互相交流
谢谢观赏
-
素数高效打表法(欧拉筛选法)
2018-10-17 19:42:12欧拉筛选法的时间复杂度仅仅为O(n)。 代码: /* 遇到素数需要打表时,先估算素数的个数: num = n / lnx; num为大概数字,越大误差越小(只是估计,用于估算素数表数组大小) 这个打表法效率貌似很高,网上说... -
筛选素数之欧拉筛法 python实现 附带证明
2018-11-03 17:07:57def oulashai(r): #返回小于r的素数列表 prime=[0 for i in range(r+1)] #全部初始化为0 common=[] #存放素数 for i in range(2,r+1): ... -
欧拉筛法求素数
2021-07-21 19:15:46欧拉筛法求素数 很多入门题目会涉及到求素数,最简单的方法就是暴力2–n-1,观察是否有能被整除的数,这也是素数的定义!复杂度O(n*n) 当然,你会发现,有些题目会超时,这时候,就是考验你如何将复杂度优化!这里有... -
欧拉质数筛选法
2018-06-04 17:21:05#include #include #include #define PressEnter \ {\ fflush(stdin); /*fflush()清空输入缓冲区的函数*/\ ...\n欧拉筛选计算用时 %d 毫秒。\n",N,num,sum,after-before); PressEnter; return 0; } //int main -
HAUT OJ 1390: 学学学学学素数--欧拉素数筛选法
2021-09-20 23:10:36乌拉拉喜欢素数,最新的一项意大利研究发现,每天做3道数学题,会使人目达耳通,秀外慧中,颖悟绝伦,七窍玲珑。一天,乌拉拉在研究素数的时候发现,所有 n>5 的素数个位数一定是1,3,7,9中的一个。于是,... -
python编写一个欧拉筛法求素数的小程序
2020-11-30 09:49:21n=eval(input()) ... # 筛选器都标记为质数 filter=[True for i in range(upperBound+1)] # 存储质数 primeNumbers=[] # 遍历所有数字 for num in range(2,upperBound+1): # 通过筛选器判断是不是质数, -
素数:欧拉筛法(自己的一些认识)
2020-08-10 15:11:06欧拉筛法(欧拉线性筛) 原理:由于所有合数都有一个最小质因子,所以在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。 精华部分(也算是对埃式筛法的优化部分): 可以发现,在下... -
数据结构与算法:欧拉筛——查找素数(质数)的最优解算法 O(n)
2022-05-04 16:10:22欧拉筛——查找素数(质数)的最优解算法 -
素数筛法 - 欧拉筛法
2019-05-07 00:39:31素数筛法 - 欧拉筛法 素数的筛法有几种,这次主要谈一下欧拉筛法 1.暴力求素数 时间复杂度 : O(n2) 稍微优化一下 :缩小数据范围从 n 优化到√n 时间复杂度 : 自然也就从 O(n2) 到 O(√n... -
欧拉筛选法求素数
2019-02-14 17:19:59#include<iostream #include<string.h> using namespace std; typedef long long ll; const ll N = 100000000; int n;... //记录当前有多少个素数 void findPrime(){ memset(vis... -
【跟着英雄学算法第⑧讲】素数筛选——枚举法+埃氏筛法+欧拉筛法(C语言实现)
2021-10-29 09:46:52✨前言✨ 在这个系列中,博主准备分享每日在万人千题社区打卡学习的算法。博主也是小白,因此也很能理解新手在刷题时的困惑,所以关注博主,每天...二、计算质数 204. 计数质数https://leetcode-cn.com/problem... -
欧拉筛选求素数
2019-12-11 15:19:26欧拉筛选求素数 简单求法: 首先,我们要明白什么是素数,素数就是一个数除了1和本身,没有其他因子的数,正整数集合可以分为3类:素数,合数和1。其中2属于素数,1既不是素数也不是合数 //首先,判断一个数是否... -
素数筛选(欧拉筛法+埃式筛法)
2022-01-27 16:21:34素数筛选(欧拉筛法+埃式筛法) -
高效素数打表 线性筛选法——欧拉筛法
2018-07-13 21:27:53素数打表,时间复杂度基本上接近O(n)代码如下:#include <iostream> #include <cstring> using namespace std; const int maxn = 10000000; bool visit[maxn+1000000]; int prime... -
详细动图展示欧拉筛法的原理
2021-12-04 20:14:25欧拉筛法是比埃氏筛法更高效的一种素数筛法,确保每个合数只被筛掉一次,算法复杂度达到O(n),被称为线性筛。 为了更好地理解它的原理,我制作了一个动态展示,配合源代码一起阅读,相信您能很快理解欧拉筛法的妙处... -
筛选素数的更高级做法(埃式筛法、欧拉筛法)
2022-01-18 18:37:01三种筛选0-100间素数的方法普通筛选:埃式筛法欧拉筛法 普通筛选: #include<iostream> #include<bits/stdc++.h> using namespace std; int main(){ int a[100]; int fag=0;//flg=0为素数,1为合数 ... -
欧拉素数筛选与命令行传参启动C程序
2020-12-02 06:46:11欧拉素数筛选与命令行传参启动C程序 不出所料,期末考试我选的就是素数筛选这道题 写了一下午,边学边写,现把成果发出来 有些逻辑还不是很好,不过就这样吧不改了 #include <stdio.h> #include <stdbool.h... -
【数据结构】欧拉函数+欧拉筛选(快来看怎么筛选出质数)
2020-07-28 20:55:42版本二:快速直接地用欧拉筛得到质数 https://blog.csdn.net/codertcm/article/details/82837259 算法简述 我们希望找到 1 - N内所有的质数。做法时标记每一个数,质数标记为0,合数标记为1。初始化每个数都是0。... -
(转载)O(N)的素数筛选法和欧拉函数
2021-03-09 21:47:07质数,只有1和其本身才是其约数,所以我们判定一个数是否为质数,只需要判定2~(N - 1)中是否存在其约数即可,此种方法的时间复杂度为O(N),随着N的增加,效率依然很慢。这里有个O()的方法:对于一个合数,其必... -
欧拉线性筛法求素数
2017-11-21 11:57:45我们先来看一下最经典的埃拉特斯特尼筛法。时间复杂度为O(n loglog n)[cpp] view plain copy print?int ans[MAXN]; void Prime(int n) { int cnt=0; memset(prime,1,sizeof(prime)); prime[0]=prime[1]=0;... -
原来 欧拉筛和埃式筛 这么简单——欧拉筛素数法和埃拉托斯特尼筛法
2020-04-13 19:11:24算法代码如下: /** *找n以内的所有素数的个数 * */ int countPrimes(int n){ //欧拉筛选法 vector<int>isPrim(n,0); //记录得到的素数,默认值为0 vector<bool>status(n,true); //记录该值的状态,默认值为true ... -
欧拉筛选法求素数 (例:洛谷P3912 素数个数)
2020-10-22 11:55:52目录前言普通筛素数欧拉筛选素数总结 前言 之前笔试写到了一个素数判断,但是超时了(尴尬,当时知道用欧拉筛,但是忘记怎么写了),于是决定写一篇博客加深下印象 。 绝对不是水博客 普通筛素数 思路:先筛掉除了2... -
【算法】Eratosthenes筛选法与欧拉筛选法求素数
2018-12-29 12:18:17Eratosthenes筛法 1.原理 一个合数可以分成几个素数的和,如果把素数(最初只知道2)的倍数全都去掉,剩下的就都是素数了 2.思路分析 去除0,1(既不是素数又不是合数) 找到队列中最小的素数,删除其倍数 3.代码实现... -
素数-欧拉筛-Python实现
2020-11-05 12:08:02返回小于n的所有素数 def EulerSieve(n: int): filter, primers = [False for _ in range(n + 1)], [] for i in range(2, n + 1): if not filter[i]: primers.append(i) for prime in primers: if i * prime &...