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<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。

Output

对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

Sample Input

2

25608

24027

Sample Output

7680

16016

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

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

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

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

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

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

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

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

代码：

// 找新朋友

#include <iostream>
#include <cmath>
#include <string.h>
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<len;++i)
	{
		j=ys[i];
		while(j<n)
		{
			prim[j]=1;
			j+=ys[i];
		}
	}
	
	sum=0;
	for(i=1;i<n;++i)
		if(prim[i]==0)
			++sum;
			
	return sum;
}

int main()
{
	int cn,num,sl,len;
	int i,j;
	
	cin>>cn;
	while(cn--)
	{
		cin>>num; 
		// 求约数，返回数组长度，数组存的就是约数 
		len=find_ys(num);
		// 看看有多少个新朋友		
		sl=search(len,num);
			
		cout<<sl<<endl;
	}
	return 0;
}