题目：找新朋友
题目描述
    新年快到了，天勤准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。
输入
    第一行是测试数据的组数CN（Case number，1<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。
输出
    对于每一个N，输出一行新朋友的人数，这样共有CN行输出。
样例输入
2
25608
24027
样例输出
7680
16016

#include <stdio.h>
#include <memory.h>
int yueshu[500],a[32770];
int zhaoyueshu(int n){//找n的约数，并返回约数的个数cnt
    int i,j=0,cnt=0;
    for(i=2;i<n;i++)
        if(n%i==0){
            yueshu[j++]=i;
            cnt++;
        }
    return cnt;
}
void Init(int n){//将数组a从第三个元素开始进行初始化
    int i;
    for(i=2;i<n;i++)
        a[i]=i;
}
void print(int n){//输出新朋友的个数
    int i,cnt=0;
    for(i=0;i<n;i++)
        if(a[i]!=0)
            cnt++;
    printf("%d\n",cnt+1);
}
int main(){
    int CN,n,cnt,i,j,t;
    scanf("%d",&CN);
    while(CN--){
        scanf("%d",&n);
        cnt=zhaoyueshu(n);
        Init(n);
        for(j=1,i=0;i<cnt;i++){
            t=yueshu[i]*j;
            while(t<n){
                a[t]=0;//将与n有共同约数的数设置为0(老朋友)，方便输出新朋友的个数
                t=yueshu[i]*(++j);
            }
            j=1;
        }
        print(n);
        memset(a,0,sizeof(a));
        memset(yueshu,0,sizeof(yueshu));
    }
    return 0;
}

提交后反馈的结果是：
    时间超限且错误50%。
但是结果我测试的都正确，不知道什么四方错了。另外我也不知道怎么优化代码，望大神纸条明路。拜谢

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include<string.h>
int a[32768];
int main()
{
    int findnew(int);
    int CN,i,*data;
    scanf("%d",&CN);
    data=(int*)malloc(CN*sizeof(int));
    for(i=0;i<CN;++i)  scanf("%d",&data[i]);

    for(i=0;i<CN;++i)  printf("%d\n",findnew(data[i]));

    free(data);

    return 0;
}
int findnew(int n)
{
    int i,j,sum;
    if(n==2) return 1;
    memset(a,0,sizeof(a));
    sum=2;

    for(i=2;i<=n-2;++i)
    {
        if(a[i]==0 && n%i==0)
        {
           for (j=i;j<=n;j+=i) a[j]=1;
        }
        if(a[i]==0) sum++;
    }
    return sum;
}

[ 本帖最后由 jklqwe111 于 2015-8-22 15:53 编辑 ]

也是超时，并且错误50%

#include <stdio.h>

int main( void)
{
    unsigned cn;
    scanf( "%u", &cn );
    while( cn-- )
    {
        unsigned n;
        scanf( "%u", &n );

        unsigned s = 0;
        for( unsigned i=1; i<n; ++i )
        {
            // 辗转相除求最大公约数
            unsigned b = i;
            for( unsigned a=n; a%b!=0; )
            {
                unsigned t = a;
                a = b;
                b = t%b;
            }

            s += (b==1);
        }

        printf( "%u\n", s );
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include<string.h>

#define BIG 32768

int ret[BIG];
int main()
{
    int findlist(int *,int);
    int CN,i,*tmp;
    
    scanf("%d",&CN);

    tmp=(int*)malloc(CN*sizeof(int));

    findlist(ret,BIG); 

    for(i=0;i<CN;++i)  scanf("%d",&tmp[i]);

    for(i=0;i<CN;++i) printf("%d\n",ret[tmp[i]]);
   
    free(tmp);

    return 0;
}



int findlist(int *data, int n)
{
    
    int i,j;

 
    memset( data,0,sizeof(int)*n);
   
    for(i=2;i<n;i++)  
    {
        if(!data[i]) 
        {
             data[i]=i-1;
            for (j=i+i;j<n;j+=i)
            {
                if(!data[j])  data[j]=(j/i)*(i-1);
                else data[j]=(data[j]/i)*(i-1);    
            }

        }
    }
    
    return 1;
}

此题就是一个欧拉函数的实现，考察数学和算法。

4楼rjsp代码也没有通过。看了好半天欧拉函数的介绍也没看懂。
我的思路是用筛法查素数的办法，由于任何一个合数都可以分解为多个质因数，所以只要这个质因数能被会长的号码整除，则这个质因数和这个质因数的倍数都是会长的老朋友，基于这种思想的代码如下(该代码提交Accepted，执行速度比5楼的慢,5楼的代码根本不需要string.h库）：
#include <stdio.h>
int findyinshu(int n)
{
    char a[32768]={0};
    int i,j,l,s;
    for(i=2,s=0;i<n;i++)
    {
        if(!a[i])
        {
            l=0;
            if(!(n%i))l=1;  //如果该素数能被会长整除，则该素数和该素数的倍数均和会长有约数，标志设为1
            s+=l;
            for(j=i+i;j<n;j+=i)
            {
                if(!a[j]||a[j]==1)
                {
                    s+=l;      //和会长有约数的计数增加
                    a[j]=1+l;  //设置素数标志和约数使用标志
                }
            }
        }
    }
    return s+1;
}
void main()
{
    int i,n,a[10000];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<n;i++)printf("%d\n",a[i]-findyinshu(a[i]));
}

[ 本帖最后由 wmf2014 于 2015-8-25 00:02 编辑 ]

原题在 http://acm.hdu.
我用4楼代码提交，超时 Time Limit Exceeded
然后改用5楼的欧拉函数（先感谢一下jklqwe111）

欧拉函数其实很简单，假设一个数n 有a、b、c……等质因数，则
有 1/a 部分能被a整除，即有 1-1/a 部分不能被a整除
有 1/b 部分能被a整除，即有 1-1/b 部分不能被b整除
有 1/c 部分能被a整除，即有 1-1/c 部分不能被c整除
……
即不能被a或b或c或……整除的部分是(1-1/a)*(1-1/b)*(1-1/c)*……
所以不含有a、b、c……质因数的数一共有 n*(1-1/a)*(1-1/b)*(1-1/c)*…… 个。
以60为例，60的质因数有2、3、5，所以少于n的数中与n互质的数的数目为 60*(1-1/2)*(1-1/3)*(1-1/5)=16。

我将jklqwe111的代码增加了一点点注释，如下

#include <stdio.h>
#include <string.h>

void euler( unsigned eulers[], size_t n )
{
    memset( eulers, 0, n*sizeof(eulers[0]) ); // 用0来区分是否为素数
    for( size_t i=2; i<n; ++i )
    {
        if( eulers[i] == 0 ) // 如果为素数
        {
            eulers[i] = i-1; // 欧拉公式 i*(1-1.0/i)
            for( size_t j=2*i; j<n; j+=i )
            {
                if( eulers[j] == 0 ) // 之前未赋值过的
                    eulers[j] = j-j/i; // 欧拉公式 j*(1-1.0/i)
                else // 之前赋值过的
                    eulers[j] = eulers[j]/i*(i-1); // 欧拉公式 ……*(1-1.0/i)
            }
        }
    }
}

int main( void )
{
    unsigned eulers[32768];
    euler( eulers, sizeof(eulers)/sizeof(eulers[0]) );

    unsigned cn;
    scanf( "%u", &cn );
    while( cn-- )
    {
        unsigned n;
        scanf( "%u", &n );

        printf( "%u\n", eulers[n] );
    }

    return 0;
}

Language: C
Exe.Time: 15MS
Exe.Memory: 1820K