这曾经对我来说是一道很难的题目。。。现在回过去在做来一遍 。。。我写这个主要是为了养成习惯！！
这个题目我做的思路是建立一个数组，通过先标记，在统计的方法！！
1 找出会长的质因数。
2 然后对各个质因数的倍数进行标记，表示老朋友。
3 统计新朋友。
代码：
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int fun(int n)
{
int i;
if(n==1) return 1;
if(n==2) return 2;
if(n%2==0) return 2;
for( i = 3; i <= sqrt(n); i += 2)
if( n % i == 0) return i;
return n;
}
int main()
{
int CN;
int i,j,n,m,count;
int a[1000];
while(scanf("%d",&CN) != EOF)
{
while( CN-- )
{
int F[32770]={0};
int k=0;
count = 0;
scanf( "%d",&n );
m = n;
while( m )
{
a[k] = fun( m );
if( m == a[k] ) break;
else
{
m /= a[k];
k ++;
}
}
for( i = 0; i <= k; i++)
{
for( j = 1; a[i]*j < n ;j ++ )
F[a[i]*j] = 1;
}
for( i = 1;i < n; i ++ )
if( F[i] == 0 ) count ++;
printf( "%d/n", count );
}
}
return 0;
}