新年快到了,"猪头帮协会" 准备搞一个聚会, 已经知道现有会员 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
- // 辗转相除法求公约数
- #include<stdio.h>
- int cmd(int a, int b)
- {
- int t=1;
- if(a<b)
- { t=a; a=b; b=t; }
- while(t!=0)
- { t=a%b; a=b; b=t; }
- return a;
- }
- int main()
- {
- int cn, n, c, i;
- scanf("%d", &cn);
- while(cn--)
- {
- c=0;
- scanf("%d", &n);
- for(i=1;i<n;i++)
- if(cmd(i,n)>1)
- c++;
- printf("%d\n", n-c-1);
- }
- return 0;
- }
- Time Limit Exceeded
- // 先打表求素数, 用 i 遍历 [2,N), 用 j 遍历 [2,i]. 寻找不大于 i 的素数 j, 判断其是否为 i 与 N 的公约数
- #include<stdio.h>
- int prime(int n)
- {
- int i, flag=1, k;
- for(i=2; i*i<=n; i++)
- if(n%i==0)
- { flag=0; break; }
- return flag;
- }
- int main()
- {
- int cn, n, c, i,j,flag, pri[32768]={0};
- for(i=2;i<=32767;i++)
- if(prime(i))
- pri[i]=1;
- scanf("%d", &cn);
- while(cn--)
- {
- c=0;
- scanf("%d", &n);
- for(i=2;i<n;i++)
- {
- flag=0;
- for(j=2;j<=i;j++)
- if(pri[j])
- if(i%j==0&&n%j==0)
- { flag=1; break; }
- if(flag) c++;
- }
- printf("%d\n", n-c-1);
- }
- return 0;
- }
- Time Limit Exceeded*2
- // Compiler Error C2103:You cannot take the address of a register.
- #include<stdio.h>
- int main()
- {
- register int cn, n;
- scanf("%d", &cn);
- while(cn--)
- {
- scanf("%d", &n);
- int a[32768]={0};
- for(register int i=2;i<=n/2;i++)
- {
- if(n%i==0)
- for(register int j=1;i*j<n;j++)
- a[i*j]=1;
- }
- int c=0;
- for(register int i=2;i<n;i++)
- c+=a[i];
- printf("%d\n", n-c-1);
- }
- return 0;
- }
- Compilation Error
- // 若一个数是 N 除 1 以外的因子, 那么它不超过 N 的倍数也是 N 的因子.
- // i 找因子, j 控制倍数, 下标为会员号码. 只有新朋友的值为 0.
- #include<stdio.h>
- int main()
- {
- int cn, n;
- scanf("%d", &cn);
- while(cn--)
- {
- scanf("%d", &n);
- int a[32768]={0};
- for(int i=2;i<=n/2;i++)
- {
- if(n%i==0)
- for(int j=1;i*j<n;j++)
- a[i*j]=1;
- }
- int c=0;
- for(int i=2;i<n;i++)
- c+=a[i];
- printf("%d\n", n-c-1);
- }
- return 0;
- }
- AC
来源: http://www.bubuko.com/infodetail-2947448.html