首页 > 代码库 > 找新朋友
找新朋友
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
1 #include <stdio.h> 2 #include <string.h> 3 4 int main(){ 5 int T; 6 int number; 7 int i; 8 int j; 9 int flag[32769]; 10 int amount;11 int temp;12 13 scanf("%d",&T);14 15 while(T--){16 scanf("%d",&number);17 memset(flag,0,32769*sizeof(int));18 temp=number;19 20 while(1){21 for(i=2;i<=number;i++){22 if(number%i==0){23 number/=i; //找出temp的因子 24 25 for(j=i;j<=temp;j+=i){ //找出因子的倍数就是目标数 26 flag[j]=1;27 }28 29 break;30 }31 }32 33 if(number==1)34 break;35 }36 37 amount=0;38 for(i=2;i<=temp;i++){39 if(flag[i]==1)40 amount++;41 }42 43 printf("%d\n",temp-amount);44 }45 return 0;46 }
找新朋友
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。