ACM-简单题之找新朋友――hdu1286 - c++编程基础

找新朋友
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6710 Accepted Submission(s): 3475

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

Input
第一行是测试数据的组数CN（Case number，1
Output
对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

Sample Input
2
25608
24027

Sample Output
7680

16016

今天花了3个小时，做了一下给大一出的提高题，

没有算法，大多数学问题吧，

唉，发现自己太粗心了，很多题，遗漏，

初始化错误，结果磨蹭几十分钟。

这道题，我用的方法跟筛法求素数差不多，

先求出来N的所有约数（1和N本身除外）

然后通过筛法，把1~N 有公共约数的筛去。

然后就简单了，遍历一遍，看看有多少个新朋友。

代码：

// 找新朋友

#include 
   
    
#include 
    
      #include 
     
       using namespace std; int ys[10001]; bool prim[33000]; int find_ys(int n) { int i,j,temp; j=0; // i从2到n/2 for(i=2;i<=n/2;++i) { if(n%i==0) ys[j++]=i; } return j; } int search(int len,int n) { memset(prim,0,sizeof(prim)); int i,j,sum; for(i=0;i
      
       >cn; while(cn--) { cin>>num; // 求约数，返回数组长度，数组存的就是约数 len=find_ys(num); // 看看有多少个新朋友 sl=search(len,num); cout<