Posted on 2010-08-17 13:24
Brian 閱讀(204)
評論(0) 編輯 收藏 引用 所屬分類:
SGU
題目簡單翻譯：對于給出的整數(shù) N (1<=N<=10
4) ，找出所有不大于N且與N互質(zhì)的正整數(shù)
個數(shù)。
兩個正整數(shù)A和B互質(zhì)的意思是它們的最大公約數(shù)是1。現(xiàn)看一下百度百科上關(guān)于
質(zhì)數(shù)的定義吧。
當(dāng)我采用直接數(shù)的辦法AC后，我發(fā)現(xiàn)跟質(zhì)數(shù)完全沒有關(guān)系。
#include<stdio.h>
int gcd(int m,int n) // greatest common divisor
{
int r=m%n;
while(r) // 輾轉(zhuǎn)相除法，TAOCP的第一個算法
{
m=n;
n=r;
r=m%n;
}
return n;
}
int main()
{
int N,c=0,i=1; // must start with 1 !
scanf("%d",&N);
for (; i<=N; i++)
if (gcd(N,i)==1) // question hint
c++;
printf("%d",c);
return 0;
}
// 102 .C Accepted 0 ms 0 kb