找新朋友
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2518 Accepted Submission(s): 1183
Problem 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
Author
SmallBeer(CML)
这里特别要说的是，求那个约数的时候不能够将 界限 定位sqrt(x) ,而应该是x本身，因为这里是要找出他的全部素数。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<time.h>int T;bool Is( int x )
{int sum=0;for( int i=1 ;i< x;++i )if( !(x%i) )sum+=i;if( sum==x )return true;elsereturn false;
}int main()
{scanf( "%d" ,&T );while(T--){int a,b,cnt=0;scanf( "%d%d" ,&a,&b );if( a>b )a^=b^=a^=b;for( int i=a ;i<=b;++i )if( Is( i ) )cnt ++;printf( "%d\n" ,cnt );}return 0;
}
思路为找出一个数大于2的约数所有约数，然后依次找他们的倍数，将他们的倍数的下标数组加上这个因子就行了。
