美文网首页
求质素(素数)

求质素(素数)

作者: 优劣在于己 | 来源:发表于2020-11-04 19:15 被阅读0次

举个例子:求2020(可泛指n)内的所有质素(素数),方法如下:
存在于个人总结,算法多种多样,看个人的思维想法吧


方法一:O(n^2)

最最最最最普通的了,就两个for循环,不想多说

int p[2020],cnt=0;
void Prime(){
    for(int i=2;i<=2020;i++){
        bool fl=true;
        for(int j=2;j<i;j++)
            if(i%j==0){
                fl=false;
                break;
            }
        if(fl)p[cnt++]=i;
    }
}

想要更快一点,无非是将 j<i 改为 j<√i


方法二:O(nloglogn)埃拉特斯特尼筛法

从2到2020(2020可泛指n)开始,先筛去n内所有2的倍数,然后每次从下一个剩下的数(必然为质数)开始,筛去其n内所有的倍数,最后剩下的数都是质数。
设置p[]储存素数
vis[]为标记数组,即0为未标记的,1为标记的,也就是某个数的倍数

int p[2020],vis[2021],cnt=0;
void Prime(){
    memset(vis,0,sizeof vis);
    for(int i=2;i<=2020;i++){
        if(!vis[i])p[cnt++]=i;
        for(int j=i*i;j<2020;j+=i)
            vis[j]=1;
    }
}

方法三:O(n)欧拉线性筛法

在第二种方法里面,会发现有合数(ps:合数即为素数的倍数,如:18=2*9=3*6)被重复筛选过了,先上代码吧

int p[2020],vis[2021],cnt=0;
void Prime(){
    memset(vis,0,sizeof vis);
    for(int i=2;i<=2020;i++){
        if(!vis[i])p[cnt++]=i;
        //cout<<"i="<<i<<endl;
        for(int j=0;j<cnt&&i*p[j]<=2020;j++){
            //cout<<" j="<<j<<" prime["<<j<<"]="<<prime[j]<<" i*prime[j]="<<i*prime[j]<<endl;
            v[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}

来解释一下里面的一些代码意思吧
首先 i*p[j] 表示地是质素的倍数了,然后标记
最核心的也就是那个跳出语句 if(i%p[j]==0)break
为什么要跳出呢,看举例子吧(本弱弱喜欢举例子,比较好理解,哈哈哈哈

i = 2
  j = 1 prime[1] = 2 i*prime[j] = 4
 i = 3
  j = 1 prime[1] = 2 i*prime[j] = 6
  j = 2 prime[2] = 3 i*prime[j] = 9
 i = 4
  j = 1 prime[1] = 2 i*prime[j] = 8
 i = 5
  j = 1 prime[1] = 2 i*prime[j] = 10
  j = 2 prime[2] = 3 i*prime[j] = 15
  j = 3 prime[3] = 5 i*prime[j] = 25
 i = 6
  j = 1 prime[1] = 2 i*prime[j] = 12
 i = 7
  j = 1 prime[1] = 2 i*prime[j] = 14
  j = 2 prime[2] = 3 i*prime[j] = 21
  j = 3 prime[3] = 5 i*prime[j] = 35
  j = 4 prime[4] = 7 i*prime[j] = 49
 i = 8
  j = 1 prime[1] = 2 i*prime[j] = 16
 i = 9
  j = 1 prime[1] = 2 i*prime[j] = 18
  j = 2 prime[2] = 3 i*prime[j] = 27
 i = 10
  j = 1 prime[1] = 2 i*prime[j] = 20
 ……
  ……

有没有看出点什么?,没有的话,我把它再单独拿出来

i = 2
  j = 1 prime[1] = 2 i*prime[j] = 4
 i = 4
  j = 1 prime[1] = 2 i*prime[j] = 8
 i = 8
  j = 1 prime[1] = 2 i*prime[j] = 16

很明显了吧,就是当 i 恰好是 p[] 的倍数的时候,就会标记 i*p[],并且跳出
i*p[] 被标记时,下一次就会标记它的倍数的,自然就只被标记了一次
倘若不跳出,就会出现合数被多次标记的情况,如:

 i = 2
  j = 1 prime[1] = 2 i*prime[j] = 4
 i = 3
  j = 1 prime[1] = 2 i*prime[j] = 6
  j = 2 prime[2] = 3 i*prime[j] = 9
 i = 4
  j = 1 prime[1] = 2 i*prime[j] = 8
  j = 2 prime[2] = 3 i*prime[j] = 12
 i = 5
  j = 1 prime[1] = 2 i*prime[j] = 10
  j = 2 prime[2] = 3 i*prime[j] = 15
  j = 3 prime[3] = 5 i*prime[j] = 25
 i = 6
  j = 1 prime[1] = 2 i*prime[j] = 12
  j = 2 prime[2] = 3 i*prime[j] = 18
  j = 3 prime[3] = 5 i*prime[j] = 30
 i = 7
  j = 1 prime[1] = 2 i*prime[j] = 14
  j = 2 prime[2] = 3 i*prime[j] = 21
  j = 3 prime[3] = 5 i*prime[j] = 35
  j = 4 prime[4] = 7 i*prime[j] = 49
 i = 8
  j = 1 prime[1] = 2 i*prime[j] = 16
  j = 2 prime[2] = 3 i*prime[j] = 24
  j = 3 prime[3] = 5 i*prime[j] = 40
  j = 4 prime[4] = 7 i*prime[j] = 56
 i = 9
  j = 1 prime[1] = 2 i*prime[j] = 18
  j = 2 prime[2] = 3 i*prime[j] = 27
  j = 3 prime[3] = 5 i*prime[j] = 45
  j = 4 prime[4] = 7 i*prime[j] = 63

再次提出来看吧

i = 4
  j = 1 prime[1] = 2 i*prime[j] = 8
  j = 2 prime[2] = 3 i*prime[j] = 12
 i = 5
  j = 1 prime[1] = 2 i*prime[j] = 10
  j = 2 prime[2] = 3 i*prime[j] = 15
  j = 3 prime[3] = 5 i*prime[j] = 25
 i = 6
  j = 1 prime[1] = 2 i*prime[j] = 12
  j = 2 prime[2] = 3 i*prime[j] = 18
  j = 3 prime[3] = 5 i*prime[j] = 30
现在应该懂了吧,over再者还有很多方法,就先到这吧

相关文章

  • 求质素(素数)

    举个例子:求2020(可泛指n)内的所有质素(素数),方法如下:存在于个人总结,算法多种多样,看个人的思维想法吧 ...

  • 求 1到100的所有素数 -- Java描述

    求 1到100的所有素数 -- Java描述 题目: 求1到100的所有素数。 例子: 素数定义: 素数又称质数,...

  • 3.判断素数、判断闰年

    一、判断素数: 定义:只能被1和它自己整除的数叫素数(质素)方法一:根据定义:对除了1和它自己的数进行取余(%)运...

  • 求素数

    求100到200的素数 输入一个大于3的数,判断是不是素数

  • 求素数

    代码如下:

  • 求素数

    初始化版本 由于只需要判断根号n前是否为素数就行了所以范围又可以缩小一般进阶改良版本

  • Python 只使用while求100以内的素数

    无聊之作求素数的方法有很多这篇文章带来一个很无聊的写法只使用while去求素数直接上代码: 常规for求素数 一起...

  • Python Day1

    愚蠢的求素数 求和

  • python 爬虫二期作业 | 第一次作业

    求1-100以内的素数 思路:直接求素数的思路当时没想好 ,就直接排除法将不是素数的从列表中删除 爬取糗事百科页面...

  • java 求素数

    按定义 即除了1和它本身以外不再被其他的除数整数 埃氏筛法 先去掉2的倍数,再去掉3的倍数,再去掉5的倍数,……依...

网友评论

      本文标题:求质素(素数)

      本文链接:https://www.haomeiwen.com/subject/zragvktx.html