精华内容
下载资源
问答
  • 欧拉筛选素数法
    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

    更多相关内容
  • 首先,得需要知道什么是“素数”。...//欧拉筛选素数法 #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的就可以了。

    展开全文
  • 1、素数筛选法(时间复杂度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;
    }
    
    展开全文
  • 素数(也称质数):只有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为大概数字,越大误差越小(只是估计,用于估算素数表数组大小) 这个打表效率貌似很高,网上说...
  • def 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
  • 乌拉拉喜欢素数,最新的一项意大利研究发现,每天做3道数学题,会使人目达耳通,秀外慧中,颖悟绝伦,七窍玲珑。一天,乌拉拉在研究素数的时候发现,所有 n>5 的素数个位数一定是1,3,7,9中的一个。于是,...
  • n=eval(input()) ... # 筛选器都标记为质数 filter=[True for i in range(upperBound+1)] # 存储质数 primeNumbers=[] # 遍历所有数字 for num in range(2,upperBound+1): # 通过筛选器判断是不是质数
  • 欧拉欧拉线性筛) 原理:由于所有合数都有一个最小质因子,所以在埃氏筛的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。 精华部分(也算是对埃式筛的优化部分): 可以发现,在下...
  • 欧拉筛——查找素数质数)的最优解算法
  • 素数 - 欧拉

    2019-05-07 00:39:31
    素数 - 欧拉 素数的筛有几种,这次主要谈一下欧拉 1.暴力求素数        时间复杂度 : O(n2) 稍微优化一下 :缩小数据范围从 n 优化到√n        时间复杂度 : 自然也就从 O(n2) 到 O(√n...
  • 欧拉筛选法素数

    千次阅读 2019-02-14 17:19:59
    #include&lt;iostream #include&lt;string.h&gt; using namespace std; typedef long long ll; const ll N = 100000000; int n;... //记录当前有多少个素数 void findPrime(){ memset(vis...
  • ✨前言✨ 在这个系列中,博主准备分享每日在万人千题社区打卡学习的算法。博主也是小白,因此也很能理解新手在刷题时的困惑,所以关注博主,每天...二、计算质数 204. 计数质数https://leetcode-cn.com/problem...
  • 欧拉筛选素数

    2019-12-11 15:19:26
    欧拉筛选素数 简单求: 首先,我们要明白什么是素数素数就是一个数除了1和本身,没有其他因子的数,正整数集合可以分为3类:素数,合数和1。其中2属于素数,1既不是素数也不是合数 //首先,判断一个数是否...
  • 素数筛选欧拉+埃式筛
  • 素数打表,时间复杂度基本上接近O(n)代码如下:#include &lt;iostream&gt; #include &lt;cstring&gt; using namespace std; const int maxn = 10000000; bool visit[maxn+1000000]; int prime...
  • 详细动图展示欧拉的原理

    千次阅读 2021-12-04 20:14:25
    欧拉是比埃氏筛更高效的一种素数,确保每个合数只被筛掉一次,算法复杂度达到O(n),被称为线性筛。 为了更好地理解它的原理,我制作了一个动态展示,配合源代码一起阅读,相信您能很快理解欧拉的妙处...
  • 三种筛选0-100间素数的方法普通筛选:埃式筛法欧拉 普通筛选: #include<iostream> #include<bits/stdc++.h> using namespace std; int main(){ int a[100]; int fag=0;//flg=0为素数,1为合数 ...
  • 欧拉素数筛选与命令行传参启动C程序 不出所料,期末考试我选的就是素数筛选这道题 写了一下午,边学边写,现把成果发出来 有些逻辑还不是很好,不过就这样吧不改了 #include <stdio.h> #include <stdbool.h...
  • 版本二:快速直接地用欧拉筛得到质数 https://blog.csdn.net/codertcm/article/details/82837259 算法简述 我们希望找到 1 - N内所有的质数。做法时标记每一个数,质数标记为0,合数标记为1。初始化每个数都是0。...
  • 质数,只有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;...
  • 算法代码如下: /** *找n以内的所有素数的个数 * */ int countPrimes(int n){ //欧拉筛选法 vector<int>isPrim(n,0); //记录得到的素数,默认值为0 vector<bool>status(n,true); //记录该值的状态,默认值为true ...
  • 目录前言普通筛素数欧拉筛选素数总结 前言 之前笔试写到了一个素数判断,但是超时了(尴尬,当时知道用欧拉筛,但是忘记怎么写了),于是决定写一篇博客加深下印象 。 绝对不是水博客 普通筛素数 思路:先筛掉除了2...
  • Eratosthenes筛 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 &...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,366
精华内容 946
关键字:

欧拉筛选素数法