程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 歐拉函數+素數篩,歐拉素數篩

歐拉函數+素數篩,歐拉素數篩

編輯:C++入門知識

歐拉函數+素數篩,歐拉素數篩


歐拉函數,就是歐拉發現的一個關於求素數的的公式,然後我們編個函數實現這個公式。

歐拉發現求小於等於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;

      }

}

 

素數篩:就是讓你判斷任意一個數是否為素數,若問一個求一個顯然會超時,所以首先需要把素數都求出來,用篩選法求的,所以叫素數篩。

原理就是若一個數有除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;

}

}

 素數篩常用於讓你判斷大量素數,或求大量素數,當然如果數目很少,就按常規判斷就好了

 

待續……

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved