CPP   80
make prime
Guest on 20th July 2022 04:35:20 PM


  1. #include<stdio.h>
  2. #include<string.h>
  3. #define MAX 100000
  4.  
  5. char prime[MAX] ;
  6. int primetable[MAX] , poi ;
  7. void make_prime( void )
  8. {
  9.     int i , j ;
  10.  
  11.     memset( prime , 1 , sizeof( prime ) ) ;
  12.     for( i=2,poi=0 ; i<MAX ; i++ )
  13.         if( prime[i] ){
  14.             primetable[poi++] = i ;
  15.             for( j=2 ; i*j<MAX ; j++ ) prime[i*j] = 0 ;
  16.         }
  17. }
  18. int count( int num )
  19. {
  20.     int sum ;
  21.  
  22.     for( sum=0 ; num ; ){
  23.         sum += num % 10 ;
  24.         num /= 10 ;
  25.     }
  26.  
  27.     return sum ;
  28. }
  29. int issmith( int num )
  30. {
  31.     int tmp_n1 , tmp_n2 , i , change ;
  32.  
  33.     if( num<MAX )
  34.         if( prime[num] ) return 0 ;
  35.     tmp_n1 = count( num ) ;
  36.     for( i=0,tmp_n2=0,change=0 ; i<poi ; )
  37.         if( !( num%primetable[i] ) ){
  38.             change++ ;
  39.             tmp_n2 += count( primetable[i] ) ;
  40.             if( tmp_n2>tmp_n1 ) return 0 ;
  41.             num /= primetable[i] ;
  42.         }
  43.         else i++ ;
  44.  
  45.     if( num>=MAX ) tmp_n2 += count( num ) ;
  46.  
  47.     if( tmp_n1==tmp_n2&&change ) return 1 ;
  48.     else return 0 ;
  49. }
  50. int main( void )
  51. {
  52.     int casetime , n , i ;
  53.  
  54. /*  freopen( "out" , "w" , stdout ) ;*/
  55.     make_prime() ;
  56.     scanf( "%d" , &casetime ) ;
  57.  
  58.     for( ; casetime ; casetime-- ){
  59.         scanf( "%d" , &n ) ;
  60.  
  61.         for( i=n+1 ; ; i++ )
  62.             if( issmith( i ) ){
  63.                 printf( "%d\n" , i ) ;
  64.                 break ;
  65.             }
  66.     }
  67.     return 0 ;
  68. }
Raw Paste

Login or Register to edit or fork this paste. It's free.