closest 素数

た入场券 2021-10-19 16:32 276阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<vector>
    #include<string>
    #include<math.h>
    #include<map>
    #include<set>
    #include<algorithm>
    using namespace std;
    
    int pri[3200];
    bool visit[3200] = {
         0};
    
    int prime( )
    {
       visit[1] = visit[0] = 1;
       int x = 50;
       for( int i = 2; i <= x; i++)
       { 
         if( !visit[i] )
         {
          for( int j = i + i; j <= 1100; j += i )
          {
            visit[j] = 1;     
          }
         }     
            
       }
       int ans = 0;
       for( int i = 1; i <= 1100 ; i++)
          if( !visit[i] )
              pri[ans++] = i;
       return ans;           
    }
    
    int Max(int x1,int x2, int x)
    {
       int a = abs(x1-x);
       int b = abs(x2-x);
       if( a == b )
           return x1;
       else if( a < b )
           return x1;
       else
           return x2;    
    }
    
    int jugde( int x , int num)
    {
      int id = lower_bound(pri, pri + num , x ) - pri;
      int x1 = pri[id];
      if( x1 == x )
          return x;
      else
      {
         if(x > 0 )
         {
            int x2 = pri[id-1];
            return Max(x1,x2,x);        
              
         }
         else
            return x1;
          
      }
      
    }
    
    int main( )
    {
      int N, T, num;
      num = prime( );
      scanf("%d",&T);
      while(T--)
      {
        scanf("%d",&N);
        printf("%d\n",jugde(N,num));
      }
      return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/08/05/2624203.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211019/20a52a3a4a7a41e184e8544e38822fb0.png