精华内容
下载资源
问答
  • 首先,得需要知道什么是“素数”。...//欧拉筛选素数法 #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;
    }
    
    展开全文
  • void init() { __int64 i, j; p[0] = 1; //记录素数个数 p[1] = 2; for (i=3; i; i+=2) { if (hash[i]) continue; p[++p[0]] = i; for (j=i*i; j; j+=i
    long long p[maxn],e[maxn];
    bool hash[maxn];
    void init()
    {
    		memset(hash,0,sizeof(hash));
    		memset(hash,0,sizeof(e));
        long long i, j;
        
        p[0] = 1; //记录素数个数
        p[1] = 2;
        for (i=3; i<N; i+=2)
        {
            if (hash[i])
                continue;
            p[++p[0]] = i;
            for (j=i*i; j<N; j+=i)
                hash[j] = true;
        } //筛素数
        
        e[1] = 1;
    
        for (i=1; i<=p[0]; i++)
            e[p[i]] = p[i] - 1; //初始化素数的phi
    
        for (i=2; i<N; i++)
        {
            if(!e[i])
            {
                for (j=1; j<=p[0]; j++)
                    if (i % p[j]==0)
                    {
                        if (i / p[j] % p[j])
                            e[i] = e[i / p[j]] * e[p[j]];
                        else
                            e[i] = e[i / p[j] ]* p[j];
                        break;
                    } // 利用上述性质求解
            }        
        }
        return ;
    }

    展开全文
  • 求10000以内的所有素数,这个问题可以使用线性欧拉筛选法,时间复杂度为O(n),上代码: public class EulerSieve { static boolean[] flag = new boolean[10001]; static int[] prime = new int[10001]; public ...

    求10000以内的所有素数,这个问题可以使用线性欧拉筛选法,时间复杂度为O(n),上代码:

    public class EulerSieve {
    
    	static boolean[] flag = new boolean[10001];
    	static int[] prime = new int[10001];
    
    	public static void main(String[] args) {
    		eulerSieve();
    		int count = 0;
    		for (int i = 0; i < prime.length; i++) {
    			if (prime[i] != 0) {
    				System.out.println(prime[i]);
    				count++;
    			}
    		}
    		System.out.println("一共有" + count + "个素数");
    	}
    
    	public static void eulerSieve() {
    		int count = 0;
    		for (int i = 2; i < flag.length; i++) {
    			if (!flag[i]) {
    				prime[count++] = i;
    			}
    			for (int j = 0; j < count && i * prime[j] < flag.length; j++) {
    				flag[prime[j] * i] = true;
    				if (i % prime[j] == 0) { //重要!
    					break;
    				}
    			}
    		}
    	}
    
    }
    
    

    运行结果:
    在这里插入图片描述
    最重要的就是break的逻辑,首先,不论一个数i是否是素数,都要用素数乘这个数来筛选掉合数,什么时候停止呢,就是i是某个素数的倍数的时候,为什么呢,详细解释,如果i%prime[j]=0,那么假设i=prime[j]乘k,即n=prime[j+1]乘i = prime[j+1]乘prime[j]乘k=prime[j]乘m
    即n这个非素数可以用prime[j]来筛选,所以不需要拿更大的素数来筛选,所以break。
    举个简单的例子,当遍历到4时,我们用2乘4筛选掉8,接下来还需要接着用3乘4筛选掉12吗?不需要了,因为我们可以用2乘6筛选掉12,如果我们用3乘4来筛选了,那遍历到6时,再用2乘6筛选,结果不会有错,但时间复杂度增加了。所以这里最关键的一点是,对于每一个合数,我们都是用它的最小质因子来筛选掉它的。所以时间复杂度为O(n)。

    展开全文
  • 欧拉筛选素数

    2019-12-11 15:19:26
    欧拉筛选素数 简单求: 首先,我们要明白什么是素数素数就是一个数除了1和本身,没有其他因子的数,正整数集合可以分为3类:素数,合数和1。其中2属于素数,1既不是素数也不是合数 //首先,判断一个数是否...
  • 欧拉筛选法素数

    千次阅读 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...
  • 目录前言普通筛素数欧拉筛选素数总结 前言 之前笔试写到了一个素数判断,但是超时了(尴尬,当时知道用欧拉筛,但是忘记怎么写了),于是决定写一篇博客加深下印象 。 绝对不是水博客 普通筛素数 思路:先筛掉除了2...
  • Eratosthenes筛 1.原理 一个合数可以分成几个素数的和,如果把素数(最初只知道2)的倍数全都去掉,剩下的就都是素数了 2.思路分析 去除0,1(既不是素数又不是合数) 找到队列中最小的素数,删除其倍数 3.代码实现...
  • 欧拉筛选法的时间复杂度仅仅为O(n)。 代码: /* 遇到素数需要打表时,先估算素数的个数: num = n / lnx; num为大概数字,越大误差越小(只是估计,用于估算素数表数组大小) 这个打表效率貌似很高,网上说...
  • 欧拉素数筛选

    2018-04-24 22:20:00
    欧拉素数: 首先: n=factormax * p 每一个合数可以表示成这样 其中 factormax为n的最大因数,p满足 1、它是素数 2、它比factormax的所有因数小 即p为n的最小素因数 证明: 假设p不是素数,那么p=p1*p2...
  • 欧拉线性求素数 回忆一下经典的埃式筛素数。时间复杂度是为O(nloglogn)(我之前一直以为是O(n))O(nloglogn)(我之前一直以为是O(n))O(nloglogn)(我之前一直以为是O(n)) int ans[MAXN]; void Prime...
  • 素数筛选 欧拉筛选

    2016-09-25 14:49:07
    #include #include const int N = 1000000 + 5; int prime[N], check[N];.../*欧拉进行素数筛选*/ void filter(int n);  int main() { memset(prime, 0, sizeof(prime)); memset(check, 0, sizeof(chec
  • 在传统的素数中,我们使用了对于每一个数n,在 1~(√n) 范围内进行取模检查,这样逐一判断的复杂度为n(√n)。但如果我们需要更快的筛时怎么办?于是著名的欧拉筛诞生了。它能将复杂度降为**O(n)**级别。1.关键...
  • 关于素数表的求,比较出名的是埃氏素数筛选法。其基本原理是每找到一个素数,将其倍数的数从素数表中删除,不断重复此过程,最终表中所剩数据全部为素数。下面的gif图片展示了该方法的相应步骤: 埃氏素数筛选法的...
  • poj2909 欧拉素数筛选

    2019-09-27 16:11:43
    刚刚学了一种新的素数筛选,效率比原先的... 这是道水题,贴代码出来重点是欧拉筛选法。我把原来普通的筛选贴出来。 //2013-11-07-22.30 //poj 2909 #include <stdio.h> #include <string.h> c...
  • #返回类型:列表#说明:返回小于upperBound的所有素数def ouLaShai(upperBound):filter=[False for i in range(upperBound+1)]primeNumbers=[]for num in range(2,upperBound+1):if not filter[num]:primeNumbers....

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 162
精华内容 64
关键字:

欧拉筛选素数法