CF396B. On Sum of Fractions

  1 /*
  2 cf396B. On Sum of Fractions
  3 http://codeforces.com/problemset/problem/396/B
  4 数论+裂项求和+素数筛+gcd
  5 */
  6 #include <cstdio>
  7 #include <algorithm>
  8 #include <cmath>
  9 using namespace std;
 10 const int Nmax=1000001;
 11 int n;
 12 int prime[Nmax];
 13 int is_prime[Nmax];
 14 int prime_cnt;
 15 long long a,b;
 16 long long gcd(long long x,long long y)
 17 {
 18     if(x%y==0)
 19         return y;
 20     else
 21         return gcd(y,x%y);
 22 }
 23 void get_prime()
 24 {
 25     for(int i=2;i<=Nmax-1;i++)
 26         is_prime[i]=1;
 27     for(int i=2;i<=Nmax-1;i++)
 28     {
 29         if(is_prime[i])
 30         {
 31             prime[++prime_cnt]=i;
 32             for(int j=2;j*i<=Nmax-1;j++)
 33             {
 34                 is_prime[i*j]=0;
 35             }
 36         }
 37     }
 38 }
 39 void get()
 40 {
 41     int flag;
 42     for(int i=n;i>=2;i--)
 43     {
 44         if(i<=Nmax-1)//i在素数表内直接判断
 45         {
 46             if(!is_prime[i])
 47                 continue;
 48             else
 49             {
 50                 a=i;
 51                 break;
 52             }
 53         }
 54         for(int j=1;j<=prime_cnt;j++)//否则枚举判断
 55         {
 56             flag=1;
 57             if(i%prime[j]==0)
 58             {
 59                 flag=0;
 60                 break;
 61             }
 62         }
 63         if(flag)
 64         {
 65             a=i;
 66             break;
 67         }
 68     }
 69     for(int i=n+1;;i++)
 70     {
 71         if(i<=Nmax-1)
 72         {
 73             if(!is_prime[i])
 74                 continue;
 75             else
 76             {
 77                 b=i;
 78                 break;
 79             }
 80         }
 81         for(int j=1;j<=prime_cnt;j++)
 82         {
 83             flag=1;
 84             if(i%prime[j]==0)
 85             {
 86                 flag=0;
 87                 break;
 88             }
 89         }
 90         if(flag)
 91         {
 92             b=i;
 93             break;
 94         }
 95     }
 96 }
 97 int main()
 98 {
 99     //freopen("cf396B.in","r",stdin);
100     int t;
101     scanf("%d",&t);
102     get_prime();//素数筛 打出Nmax内的素数表
103     while(t--)
104     {
105         scanf("%d",&n);
106         get();//得到不超过n的素数a和大于n的素数b
107         long long p=a*b-2*b+2*n-2*a+2,q=2*a*b;
108         //约分
109         long long gcdd=gcd(p,q);
110         p=p/gcdd;
111         q=q/gcdd;
112         printf("%I64d/%I64d
",p,q);
113     }
114     return 0;
115 }