Brian Warehouse

Some birds aren`t meant to be caged, their feathers are just too bright... ...
posts - 40, comments - 16, trackbacks - 0, articles - 1

SGU 102 Coprimes

Posted on 2010-08-17 13:24 Brian 阅读(181) 评论(0)  编辑 收藏 引用 所属分类: SGU
题目简单翻译:对于给出的整数 N (1<=N<=104) ,找出所有不大于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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理