输入几个数，输出每个数小于它且没公约数的数的个数。（输入个数无限制）下面是小弟写的，但用时太长，望高手能展现你的能力，帮我解难。Thank you!
#include <stdio.h>
int flag(int a,int b)
{    int j,n;
    while((j=a%b)!=0)
    {a=b;
     b=j;
     n=b;
    }
    if(n!=1) n=0;
    return(n);
}
void main()
{
    int n,i,j;
    while(scanf("%d",&n)!=EOF)
    {j=1;
     for(i=1;i<n;i++)
     if(flag(n,i))  j++;
     printf("%d\n",j);
    }
}

[[it] 本帖最后由 xjp814 于 2008-4-24 22:02 编辑 [/it]]

最佳时间复杂度应该是O(sqrt(n))
你的用了O(n)，当然慢

注意，你要是说精简的话，那就已经没什么好精简了

" border="0" />[color=white]

收到的鲜花

• xjp814 于 2008-04-24 22:24 送鲜花  1朵   附言：虽然收获不大，但谢了。

虽然收获不大，但谢了。