HDU-1286-找新朋友

​​题目链接​​

找新朋友

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 的倍数