Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 5 Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。
Input
第一行是测试数据的组数CN（Case number，1
#include<stdio.h> #include<string.h> #define maxn 35000 int a[maxn]; int main() { int cn; scanf("%d",&cn); while(cn--) { int n,i,j,ans=0; scanf("%d",&n); memset(a,-1,sizeof(a)); for(int i=2;i<n;i++) { if(n%i==0) for(j=1;j*i<n;j++) a[i*j]=0; } //此处是素数打表，经常用到的具体原理可以查阅欧拉函数详解 for(i=2;i<n;i++) if(a[i]==0) ans++; printf("%d\n",n-ans-1); } return 0; }
//这里在介绍几种素数查找的方法（这几个都是自定义函数） #include<stdio.h> int isprime(int n) { if(n<2) return 0; for(int i=2; i*i<n; i++) if(n%i==0) return 0; return 1; } int main() { } #include<stdio.h> int isprime(int n) { int i; for(i=2;i<n/2;i++) if(n%i==0) break; if(i>n/2&&n>1) return 1; else return 0; } #include<stdio.h> #define maxn 1000000 int table[maxn]; int buildprimetable() { table[1]=1; //第 0 个不需要 for(int i=2;i*i<maxn;i++) if(!table[i]) //不是素数的跳过 for(int j=i*i;j<maxn;j+=i) table[j]=1; //包含因子 i 的不是素数，标记为 1 } #include<stdio.h> #define maxn 100000000 bool notprime[maxn+5]; int Screeningprime() { int i,j,increment[6]={0,4,0,0,0,2}; for(i=5;i*i<=maxn;i+=increment[i%6]) { for(j=i;i*j<=maxn;j+=increment[j%6]) { notprime[i*j]=true; } } } /*素数出现的规律： 当 n>=5 时，如果 n 为素数，那么 n mod 6 = 1 或 n mod 6 = 5，即 n 一定出现在 6x (x>=1) 两侧。 证明： 当 下 x>=1 时有如下表示方法： ......6x, 6x+1, 6x+2, 6x+3, 6x+4, 6x+5, 6(x+1), 6(x+1)+1....... 不在 6x 两侧的数为 6x+2, 6x+3, 6x+4,即 2(3x+1), 3(2x+1), 2(3x+2),他们一定不是素数，所以素数一定出现在 6x 两侧。 可以根据下面结论写代码： 若 x>=1 且 n=6x-1 或 n=6x+1不是素数，那么 n 一定不是 2和3 的倍数 证明： 因为 n=6x-1 或 n=6x+1，即 n=2(3x)-1 或 n=2(3x)+1 或 n=(3x)-1 或 n=3(2x)+1 所以 n 一定不是 2和3 的倍数
