精华内容
下载资源
问答
  • 筛选法

    千次阅读 2019-07-20 18:41:12
    筛选法又称筛法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3...

    筛选法又称筛法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上,每要划去一个数,就在上面记以小点,寻求质数的工作完毕后,这许多小点就像一个筛子,所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”,简称“筛法”。(另一种解释是当时的数写在纸草上,每要划去一个数,就把这个数挖去,寻求质数的工作完毕后,这许多小洞就像一个筛子。)
    //用筛选法求100之内的素数:
    #include<stdio.h>

    void Primenumber()
    {
    int arr[100];
    int i;
    int j;
    //1不是素数,从2开始
    for(i=2;i<100;i++)
    {
    arr[i]=i;
    for(j=2;j<i;j++)
    {
    //能被它前面的数整除的,说明不是素数,都淘汰掉。
    if(arr[i]%j==0)
    {
    arr[i]=0;
    }
    }
    //把素数输出。
    if(arr[i]!=0)
    {
    printf("%d\n",arr[i]);
    }
    }
    }

    int main()
    {
    Primenumber();
    return 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;
    }
    
    展开全文
  • c++素数筛选法

    2020-08-30 09:32:09
    本文讲的是筛选法的C++实现, 筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛子。
  • 杭电ppt筛选法

    2019-01-20 10:53:58
    杭电ppt筛选法及预处理。
  • import java.util.ArrayList;.../*** 筛选法求素数* @author wl**/public class FilterPrime {private final static int N=1000;public static void main(String[] args) {List list=getPrime(N);Syste...

    import java.util.ArrayList;

    import java.util.List;

    /**

    * 筛选法求素数

    * @author wl

    *

    */

    public class FilterPrime {

    private final static int N=1000;

    public static void main(String[] args) {

    List list=getPrime(N);

    System.out.println(N+"以内的素数有:"+list.size()+"个!!!");

    for(int i=0;i

    System.out.print(list.get(i)+",");

    if((i+1)%10==0){

    System.out.println();

    }

    }

    }

    public static List getPrime(int n){

    List list=new ArrayList();

    int minPrime=2;//最小素数

    int doub;

    int[] arr=new int[n+1];

    for(int j=2;j<=n;j++){//初始化arr数组,将2——N的下标对应的值初始化为1;

    arr[j]=1;

    }

    while(minPrime

    /**

    * 以下为将minPrime的n倍(n=2,3,4,5......)标记为0;

    */

    doub=2*minPrime;//minPrime的2倍

    while(doub

    arr[doub]=0;

    doub=doub+minPrime;//minPrime的3倍、4倍.......

    }

    do{

    minPrime++;

    }while(arr[minPrime]==0);//arr[minPrime]==0时说明minPrime不是素数,应该minPrime++;

    }

    for(int m=2;m

    if(arr[m]==1){

    list.add(m);

    }

    }

    return list;

    }

    }

    结果为:

    1000以内的素数有:168个!!!

    2,3,5,7,11,13,17,19,23,29,

    31,37,41,43,47,53,59,61,67,71,

    73,79,83,89,97,101,103,107,109,113,

    127,131,137,139,149,151,157,163,167,173,

    179,181,191,193,197,199,211,223,227,229,

    233,239,241,251,257,263,269,271,277,281,

    283,293,307,311,313,317,331,337,347,349,

    353,359,367,373,379,383,389,397,401,409,

    419,421,431,433,439,443,449,457,461,463,

    467,479,487,491,499,503,509,521,523,541,

    547,557,563,569,571,577,587,593,599,601,

    607,613,617,619,631,641,643,647,653,659,

    661,673,677,683,691,701,709,719,727,733,

    739,743,751,757,761,769,773,787,797,809,

    811,821,823,827,829,839,853,857,859,863,

    877,881,883,887,907,911,919,929,937,941,

    947,953,967,971,977,983,991,997,

    展开全文
  • Eratosthenes筛选法与欧拉筛选法

    千次阅读 2015-08-14 17:40:59
    Eratosthenes筛选法 由于一个合数总是可以分解成若干个质数的乘积,那么如果把质数的倍数都去掉,那么剩下的就是质数了.Eratosthenes筛选法的思想特别简单:对于不超过n的每个非负整数p,删除2p,3p,4p,...,当处理完...
    Eratosthenes筛选法与欧拉筛选法
    由于一个合数总是可以分解成若干个质数的乘积,那么如果把质数的倍数都去掉,那么剩下的就是质数了.Eratosthenes筛选法的思想特别简单:对于不超过n的每个非负整数p,删除2p,3p,4p,...,当处理完所有数之后,还没有被删除的就是素数.如果用vis[i]表示i已经被删除,则筛选法的代码可以写成:
    void isprime(int n)///筛选1-n的素数
    {
        memset(vis,0,sizeof(vis));
        for(int i = 2; i <= n; i++)
            for(int j = 2 * i; j <= n; j += i)
                vis[j] = 1;
    }
    尽管代码已经相当高效了,但仍然可以进行改进.首先,在"对于不超过n的每个非负数p"中,p可以限定为素数--只需在第二重循环前加一个判断if(!vis[i])即可.另外,内层循环也不必从* 2开始--它已经在= 2时被筛选了.改进后代码如下:
    void isprime(int n)///筛选1-n的素数
    {
        memset(vis,0,sizeof(vis));
        int m = sqrt(n + 0.5);
        for(int i = 2; i <= m; i++)
        {
            if(!vis[i])
            {
                for(int j = i * i; j <= n; j += i)
                    vis[j] = 1;
            }
        }
    }

    Eratosthenes筛选法虽然效率高,但是Eratosthenes筛选法做了许多无用功,一个数会被筛到好几次,最后的时间复杂度是O(nloglogn),对于普通素数算法而言已经非常高效了,但欧拉筛选法的时间复杂度仅仅为O(n).

    欧拉筛选法的思想就是不做无用功,原本Eratosthenes筛法的第一重循环是用来找素数,然后把素数的倍数标记,而欧拉筛法换了一个角度,第一位是找素数没有问题,但是标记的时候用的是所有数.欧拉筛选法在数据小的时候不如Eratosthenes筛选法快,反而是数据变大以后,两者差距变得越来越明显,欧拉筛选法明显快于Eratosthenes筛选法.欧拉筛选法代码如下:

    const int Max = 100002;
    int Prime[Max];
    bool vis[Max];
    void prepare()
    {
        int num = 0;
        memset(vis,true,sizeof(vis));
        for(int i = 2; i <= Max; ++i)
        {
            if(vis[i])
                Prime[++num] = i;
            for(int j = 1; j <= num; ++j)
            {
                if (i * Prime[j] > Max)
                    break;
                vis[i * Prime[j]] = false;
                if (i % Prime[j] == 0)
                    break;
            }
        }
    }


    展开全文
  • 素数筛选法

    千次阅读 2018-12-30 11:22:34
    素数筛选法 素数筛选法的目的就是筛选出在某一区间[m,n)内的所有素数,常见的办法有如下几种。 1.朴素的筛选法 朴素的筛选法思路很简单,先写一个判断是否是素数的函数isPrime(),然后从2到n分别调用isPrime()...
  • 易语言Eratosthenes筛选法求质数源码,Eratosthenes筛选法求质数,Eratosthenes筛选法_求质数
  • 高效筛选法

    2019-10-01 20:34:29
    先实现高效的素数筛选法 然后再暴力的无平方数筛选法 然后再高效的平方数筛选法 bool vis[1000000 + 5]; //首先实现最高效的素数筛选 void creat_primer_table(int m) { for(int i = 2;i * i <= m;i++)...
  • 今天记录一下如何用埃拉托色尼筛选法实现输出小于某个数n的所有质数,大家都知道质数是除了自己和1之外的所有数整除的数。最粗暴的实现方法就是用两个for循环,在最里层进行取余操作,如果取余为0则不是质数。除此...
  • 埃拉托色尼筛选法

    2017-10-05 23:58:27
    埃拉托色尼筛选法
  • python素数筛选法浅析

    2020-09-20 17:00:50
    主要为大家详细介绍了python素数筛选法的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 筛选法的C++实现

    2020-09-04 23:17:12
    筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛子

空空如也

空空如也

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

筛选法