Posted on 2010-08-17 13:24
Brian 閱讀(208)
評論(0) 編輯 收藏 引用 所屬分類:
SGU
題目簡單翻譯：對于給出的整數 N (1<=N<=10
4) ，找出所有不大于N且與N互質的正整數
個數。
兩個正整數A和B互質的意思是它們的最大公約數是1。現看一下百度百科上關于
質數的定義吧。
當我采用直接數的辦法AC后，我發現跟質數完全沒有關系。
#include<stdio.h>
int gcd(int m,int n) // greatest common divisor
{
int r=m%n;
while(r) // 輾轉相除法，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