C語言算一個數(shù)歐拉函數(shù)，輸入0結束

unsigned int ss(unsigned int a)

網(wǎng)站建設哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、微信小程序開發(fā)、集團企業(yè)網(wǎng)站建設等服務項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了讓胡路免費建站歡迎大家使用！

{

unsigned int i;

for(i=2;i*i=a;i++) {

if(a%i==0) break;

}

if(i*i=a) return 0;

else return 1;

}

這個判斷素數(shù)的函數(shù)邏輯是：

i在2~根號a（a是外部傳入的需要判斷的正整數(shù)）之間循環(huán)遞增1，

如果a能被i整除，則跳出循環(huán)，否則繼續(xù)循環(huán)直至i大于根號a退出循環(huán)，

退出循環(huán)后，判斷當前i值是否小于根號a，

小于等于根號a，則是中途退出，返回0（是合數(shù)）；

大于根號a，則是循環(huán)條件完成退出，返回1（是質(zhì)數(shù)）。

函數(shù)ss( a)在函數(shù)unsigned int oula(unsigned int n)中調(diào)用

unsigned int oula(unsigned int n)

{

unsigned int f=n,p;

for(p=2;p=n;p++)

if(ss(p)(n%p==0)) f=f*(1-(1/p));? 調(diào)用處

return f;

}

輸入100,000,000，要看編譯器對unsigned int的定義，

如果編譯器定義為2 byte，則范圍是：0~2^16-1(62353)，此時100,000,000會溢出。

如果編譯器定義為4 byte，則范圍是：0~4294967295,大于100,000,000.此時可以輸入，但因數(shù)據(jù)太大，計算完成要超過2分鐘（用去年主流配置的x86電腦測試），輸入10,000,000就感覺明顯的時延，要約20秒才能輸出結果。

測試截圖如下圖：

另，函數(shù)unsigned int oula(unsigned int n)需要改成：

unsigned int oula(unsigned int n)

{

unsigned int f=n,p;

for(p=2;p=n;p++)

if(ss(p)(n%p==0))

//f=f*(1-(1/p));? //修改小數(shù)部分丟失問題

f=f*(p-1)/p;

return f;

}

供參考。

什么是歐拉函數(shù)

在數(shù)論，對正整數(shù)n，歐拉函數(shù)math\varphi(n)/math是少于或等于n的數(shù)中與n互質(zhì)的數(shù)的數(shù)目。此函數(shù)以其首名研究者歐拉命名，它又稱為Euler's totient function、φ函數(shù)、歐拉商數(shù)等。

例如math\varphi(8)=4/math，因為1,3,5,7均和8互質(zhì)。

從歐拉函數(shù)引伸出來在環(huán)論方面的事實和拉格朗日定理構成了歐拉定理的證明。

[編輯]φ函數(shù)的值

math\varphi(1)=1/math（唯一和1互質(zhì)的數(shù)就是1本身）。

若n是質(zhì)數(shù)p的k次冪，math\varphi(n)=p^a-p^=(p-1)p^/math，因為除了p的倍數(shù)外，其他數(shù)都跟n互質(zhì)。

歐拉函數(shù)是積性函數(shù)——若m,n互質(zhì)，math\varphi(mn)=\varphi(m)\varphi(n)/math。證明：設A, B, C是跟m, n, mn互質(zhì)的數(shù)的集，據(jù)中國剩余定理，mathA \times B/math和C可建立一一對應的關系。因此math\varphi(n)/math的值使用算術基本定理便知，

若mathn = \prod_{p\mid n} p^{\alpha_p}/math，

則math\varphi(n) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}\left(1-\frac\right)/math。

例如math\varphi(72)=\varphi(2^3\times3^2)=2^(2-1)\times3^(3-1)=2^2\times1\times3\times2=24/math

[編輯]與歐拉定理、費馬小定理的關系

對任何兩個互質(zhì)的正整數(shù)a, m，mathm\ge2/math，有

matha^{\varphi(m)} \equiv 1 \pmod m/math

即歐拉定理

當m是質(zhì)數(shù)p時，此式則為：

matha^ \equiv 1 \pmod p/math

即費馬小定理。

C語言實現(xiàn)歐拉函數(shù)

int eular(int n)

{

int ret=1,i; //定義變量

for(i=2;i*i=n;i++) //從i=2開始循環(huán)，判定條件為i*i小于等于n，循環(huán)一次i增加1

if(n%i==0) //判定條件為n除以i的余數(shù)等于0

{

n/=i,ret*=i-1; //n=n/i，ret = ret*(i-1)

while(n%i==0) //當n除以i的余數(shù)等于0時執(zhí)行下面的語句，否則跳過

n/=i,ret*=i;

}

if(n1) //如果n1執(zhí)行下面語句，否則跳過

ret*=n-1; //ret = ret*(n-1)

return ret;

}

直接復制的百度百科的，沒具體看是什么功能

C語言求解歐拉函數(shù)和本原根

#include?stdio.h

int?eulerFunc(int?n,?int*?num_out)?{

int?i,?j,?cnt?=?0;

num_out[cnt++]?=?1;

for?(i?=?2;?i?=?n;?++i)?{

for?(j?=?2;?j?=?i;?++j)?{

if?(i?%?j?==?0??n?%?j?==?0)?{

break;

}

}

if?(j??i)?{

num_out[cnt++]?=?i;

}

}

return?cnt;

}

int?main(void)?{

int?n,?num[10],?y,?i;

scanf("%d",?n);

y?=?eulerFunc(n,?num);

for?(i?=?0;?i??y;?++i)?{

printf("%d?",?num[i]);

}

printf("\n%d",?y);

return?0;

}