ACM-簡單題之找新朋友——hdu1286

找新朋友
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<