Description
新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

Input
第一行是测试数据的组数CN（ Case number，1 < CN < 10000 ），接着有CN行正整数N（ 1 < n < 32768 ），表示会员人数。

Output
对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

Sample Input
2
25608
24027 Sample Output
7680
16016
我的程序：
#include<stdio.h>
int f(int n)
{   
    int j,d,k;      
    d=0;
    for (j=2;j<n;j++)
    for (k=2;k<=j;k++) if (n%k==0 && j%k==0) {d++;break;}
    return d;
}
void main()
{
    int i,n,t;
    while(scanf("%d",&t)!=EOF)
    {
        for (i=0;i<t;i++)
        {
            scanf("%d",&n);
            printf("%d\n",n-f(n)-1);
        }
    }
}
怎么又超时了啊。。。求高手教一些能够简化的方法，对于这些容易超时的题目。

欧拉函数，这样求每个f(n)时时间复杂度可以由O(N)简化到O(sqrt(n))

试试,应该好多了!
int f(int n)
{   
    int j,d,k;      
    d=0;
    if(n%2==0){
        for (j=3;j<n;j+=2,d++)
        for (k=3;k<=j;k+=2) if (n%k==0 && j%k==0) {d++;break;}
    }
    else{
        for (j=3;j<n;j++)
        for (k=3;k<=j;k+=2) if (n%k==0 && j%k==0) {d++;break;}
    }
    return d;
}

[ 本帖最后由 cnfarer 于 2011-12-3 17:28 编辑 ]

听说过欧拉公式没？

这个，小弟才疏学浅，还真不知道欧拉公式，求讲解一下，谢谢

数论中的欧拉公式，自己查资料吧。
下面的代码即是用欧拉公式并结合了素数筛法的解题算法。杭电1286题，0ms AC。

#include<stdio.h>
int f[32768];
void init()
{
    char a[32768] = {0};
    int i, j, c;
    for(i = 2; i < 32768; i++) f[i] = i;
    for(i = 2; i < 32768; i++)
    {
        if(a[i])continue;
        c = i - 1;
        for(j = i; j < 32768; j += i)
        {
            f[j] /= i;
            f[j] *= c;
            a[j] = 1;
        }
    }
}
int main()
{
    int c, n;
    init();
    scanf("%d", &c);
    while(c--)
    {
        scanf("%d", &n);
        printf("%d\n", f[n]);
    }
    return 0;
}