বৃহস্পতিবার, ২২ ডিসেম্বর, ২০১৬

UVA-914 - Jumping Champion

#include <stdio.h>
#include <math.h>
#include<bits/stdc++.h>
using namespace std;

#define SIZE 1000001

long long ar[1000010]={0}, status[SIZE],k=0;
 vector<long int>prime;
void sieve()
{
 int i,j;
 for(i=0;i<SIZE;i++) status[i]= 0;
 int sq = sqrt(SIZE);
 status[1] = 1,status[0] = 1;

 for(i=3;i<=sq;i+=2)
   {
      if(status[i]==0)
       {
            for(j=2*i;j<=SIZE;j+=i)
             status[j]=1;
       }
   }
   for(i=2;i<=SIZE;i++)
   {
       if(i%2==0&&i!=2)
       {
           continue;
       }
       else
       {
           if(status[i]==0)
           {
               prime.push_back(i);
           }
       }
   }
   k=prime.size();
}

int main()
{

 sieve();
 long long ts;
 cin>>ts;
 while(ts--)
 {
      long long int n,m,ans,mx=0,cnt=0,i1,vs,differ[200]={0},k1=0,low=0,high=0,k2=0;
      cin>>n>>m;
      for(i1=0;i1<k;i1++)
      {
          if(prime[i1]>=n&&cnt==0)
          {
              low=i1;
              cnt++;
          }
          else if(prime[i1]<=m)
          {
              high=i1;
          }
      }
     if(cnt!=0)
      {
          for(i1=low+1;i1<=high;i1++)
          {
              k1=prime[i1]-prime [i1-1];
              differ[k1]++;
          }
          for(i1=0;i1<=120;i1++)
          {
              if(differ[i1]>differ[k2])
              {
                  k2=i1;
              }
          }
          sort(differ,differ+120);
          if(differ[118]==differ[119])
          {
              printf("No jumping champion\n");
          }
          else
            printf("The jumping champion is %lld\n",k2);
      }
    else
      {
          printf("No jumping champion\n");
      }
 }
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...