看到一个求素数的题目,忽然想试试欧拉筛有多快。

欧拉函数+素数筛,欧拉素数筛

题目:求一千万内素数的个数。

欧拉函数,就是欧拉发现的一个关于求素数的的公式,然后我们编个函数实现这个公式。

欧拉发现求小于等于n的正整数中有多少个数与n互质可以用这个公式:

euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数,x是不为0的整数。euler(1)=1(唯一和1互质的数就是1本身)。 

欧拉公式的延伸:一个数的所有质因子之和是euler(n)*n/2。

其实直接看模板加注解想想就能看懂

筛选的原理就是找出n的因子,剔除含有n的因子的数,即剔除与n不互质的数

既然是求与n互质的个数,那我们可以直接筛选,看模板:

int phi(int n)

{    int res=n;                  /假设现有n个数与n互质,开始筛选剔除

 for(i=2;i*i<=n;i++)

{    if(n%i==0)              
 /若这个数是n的因子,减去n以下含有这个因子的数个数,假设n=8,小于等于8,2为公因子的有8/2=4个

   {   res-=res/i;

       while(n%i==0)            /将n不断整除这个因子  

       n=n/i;

    }

}

if(n>1)             /若n大于1,则此时的n也是一个除1以外的因子

res-=res/n;            

return res;

}

有时候还用到多个数的欧拉值,因此需要对1到n的数都求出欧拉值,就是打表。

将1到n的欧拉值求出并存储到数组,筛选法,代码:

void phi(int n)                        
上边的看懂了,下边这个求多个数的也类似

{   for(int i=1;i<=n;i++)

     p[i]=i;                   赋原值

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

      if(p[i]==i)                

      {   for(int j=i;j<=n;j+=i)          筛选

澳门新萄京官方网站,           p[j]=p[j]-p[j]/i;

      }

}

先看最普通的筛子:1077秒

 

T = os.time()

--求iMaxN内的素数
local iMaxN = 10000000

--普通筛子
local iSS = {}  --素数数组
local iSZ = {}  --筛子
for i = 1, iMaxN do
    iSZ[i] = i
end

--过筛求出所有素数
for i = 2, math.sqrt(iMaxN) do
    for j = i + 1, iMaxN do
        if (j % i) == 0 then
            iSZ[j] = 0  --非素数置0
        end
    end
end

for i = 2, iMaxN do
    if iSZ[i] > 0 then
        iSS[#iSS + 1] = i   --放入素数数组
    end
end

print('用时:', os.time() - T)

print(#iSS)

os.execute('PAUSE')

素数筛:就是让你判断任意一个数是否为素数,若问一个求一个显然会超时,所以首先需要把素数都求出来,用筛选法求的,所以叫素数筛。

原理就是若一个数有除1和它本身以外的因子就将它标记不是素数,最后无标记的就是素数。

直接看代码加注解:

#include <iostream>

#include <cstring>

#define MAX 1000001

int flag[MAX];

int main()

{    memset(flag,0,sizeof(flag));

     flag[1]=1;               /1代表不是素数,0代表是素数

    for(int i=4;i<MAX;i+=2)

      flag[i]=1;              /先将偶数先标记不是

    for(int i=3;i*i<MAX;i+=2)  

    for(int j=i*i;j<MAX;j+=i)   /奇数的倍数标记不是

      flag[j]=1;

int n;                           

while(cin>>n)

{   if(flag[n]==0)

    cout<<“YES”<<endl;

    else

   cout<<“NO”<<endl;

}

}

 素数筛常用于让你判断大量素数,或求大量素数,当然如果数目很少,就按常规判断就好了

 

待续……

欧拉函数,就是欧拉发现的一个关于求素数的的公式,然后我们编个函数实现这个公式。
欧拉发现求小于等…

网站地图xml地图