专栏首页ACM算法日常三种素数筛的比较

三种素数筛的比较

在自然数集中,质数的数量不多而且分布比较稀疏,对于一个整数N,不超过N的质数大概有N/lnN个,即每lnN个数中可能会有一个质数。

在筛选0—N中的素数的方法较多:

1.试除法

bool is_prime(int n)
{
    for(int i=2;i<=sqrt(n);i++)
         if(n%i==0)return false;
   return true;
}

2.Eratosthenes筛选法

想法是:任意整数x的倍数 2x,3x,..都不会是质数

我们从2开始扫,从小到大扫每个数x,把他的倍数2x,3x,...,[N/x]*x标记为合数.

扫到一个数时,它不被2—x-1之间任何数整除,该数即为质数

当然,我们会发现,2和3都会把6标记为合数。

由此我们可知,小于x^2的x的倍数在扫更小的数时已经被扫了一遍。

就不必像2和3都会把6扫一遍那样多余的白白浪费运算时间了。

我们要做的就是对这个算法进行优化

:对于每个数x,我们只需从x^2开始扫,把x^2,(x+1)*x,...,[N.x]*x标记合数即可。

void primes(int n)
{
     memset(v,0,sizeof(v));//标记合数
     for(int i=2;i<=n;i++)
     {
          if(v[i])continue;
          else cout<<i<<endl;//看是不是质数,是质数的话输出
          for(int j=i;j<=n/i;j++)v[i*j]=1;
     }
}

当然这篇blog到此不会截止,我想说的是:虽然.Eratosthenes筛选法是让素数x从x^2往上开始2筛的,但还是会造成重复筛选。

就像2和3都会把6标记为合数一样,

虽然Eratosthenes筛选法是把x^2,(x+1)*x,...,[N.x]*x标记合数

但还是会造成重复筛选。

如:12=6*2,12=4*3,很明显12被重复筛选了,

Eratosthenes筛选法 的本质和爆破的试除法 一样,只不过减少了重复筛选的次数。

而我们想知道的是产生一个合数的唯一方式。

这时我们讲一下线性筛:

举个简单的例子:我们通过 从小到大累积质因子 来标记每个合数,让12=3*2*2是合数组成的唯一的方式

线性筛是通过 从小到大累积质因子 来标记每个合数,当我们理解这句话的含义时,实现代码就不难了

int v[maxn],prime[maxn];//prime用来记载质数
void primes(int n)
{
       memset(v,0,sizeof(v));
       m=0;//最小质因子
       for(int i=2;i<=n;i++)
       {
            if(v[i]==0)
             { v[i]=i;prime[++m]=i; }//i是质数的话

           //让当前数i乘上一个质因子
            for( int j=1;j<=m;j++)
             {
                 //i有比prime[j]更小的质因子  或超出n的范围停止
                  if(prime[j]>v[i] ||prime[j]>n/i )break;
                 //prime[j]是合数i*prime[j]的最小质因子
                  v[i*prime[j]]=prime[j];
             }
       }
            for(int i=1;i<=m;i++)cout<<prime[i]<<endl;
}

这种方法省时就省时在,不会造成重复筛选!

其实关于质数的题目还有一个应用就是:质因数分解

pi序列都为质数,ci为次幂

对任何N,都有:

N=p1^c1*p2^c2.......

由此可以利用 试除法 和 Eratosthenes筛选法 完成质因数分解:

其实 它的一个更好的应用是求最大质因子 因为一个数字不可能有两个大于根号的因子,还是素因子所以我们函数内,for循环的条件是:

for(int i=2;i<=sqrt(n);i++)

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn=1e5;
long long p[maxn];
long long c[maxn];
void divide(int n)
{
        int m=0;
        for(int i=2;i<=sqrt(n);i++)
        {
                   if(n%i==0)//i为质数
                  {
                           p[++m]=i;c[m]=0;
                          while(n%i==0)
                           {
                                   n/=i;c[m]++;
                           }
                  }
        }   //最后剩余的数不能为任何区间内质数整除,则剩余的数              也为质数
            if(n>1)
            {p[++m]=n;c[m]=1;   }

       for(int i=1;i<=m;i++)
            cout<<p[i]<<" "<<c[i]<<endl;
}
int main()
{
    int n;cin>>n;
    divide(n);
    return 0;
 }

本文分享自微信公众号 - ACM算法日常(acm-clan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 王者荣耀爆款H5有何过人之处?

    敦煌壁画是我们民族引以为傲的瑰宝 但是它的绚丽正在一点点消失... 腾讯联合王者荣耀和敦煌研究院 最近发起了一个数字供养人计划 希望有更多人了解和热爱敦煌 为...

    腾讯大讲堂
  • React Native在Windows下修改js代码后reload无效

    iOS下因为有watchman这个插件,所以启动很快(npm start),而Windows下则非常慢,最要命的是遇到了修改js文件后,点击reload居然一直...

    meteoric
  • 手游推广方面的一些想法

    举个实际的例子,就是xx游戏xx区的A玩家,他通过游戏内的分享功能,分享一个链接至社交平台之后,通过该玩家分享的链接进行下载的玩家对A有一个返利,比如下载次数(...

    meteoric
  • PhoneGap Build的使用

          纯粹属于闲折腾的结果,只是这中间还遇到一些问题,记录一下。因为没有IOS的开发key,所以这里只发布成功Android系统的安装程序。之前写过一篇构...

    meteoric
  • 国际化之Android设备支持的语种

    昨天发了关于iOS支持的语种,文章最后也补了安卓支持语种列表。但最后发现安卓设备支持跟它列的有出入,我重新完全手工整理了一遍。

    meteoric
  • DELL R710 服务器内存排错

    man dmidecode 可以得到详细的介绍和使用方法,dmidecode - DMI table decoder,DMI (Desktop Manageme...

    三杯水Plus
  • C++学习笔记 -- 虚析构函数与纯虚析构函数

    一个类维护一个虚函数相关的表--vtable(__vfptr指向它),函数声明前面包含关键字“virtual”的函数,就会创建一个指向该函数的指针(函数指针)被...

    meteoric
  • cocos2d-x绑lua的开发环境

    2013年是手游开发井喷的一年,也是手游市场竞争最为激烈的一年,ios市场除了刷榜、刷榜,还是刷榜,而android有点像黑市的感觉,水太深(很多渠道商已经从上...

    meteoric
  • 国际化之iPhone设备支持的语种

    有没有想过,iPhone 语言到底支持多少语言呢?我倒是搜索了一下,整理出下面一份列表,供大家参考

    meteoric
  • 移动开发工具推荐

    Android:豌豆夹,快速连接手机的利器。腾讯的应用宝也好,360的手机助手也好,在插入USB之后,确实不如豌豆夹好使,谁用谁知道。如果连接了USB还是不能识...

    meteoric

扫码关注云+社区

领取腾讯云代金券