C   20

divide prime

Guest on 6th June 2022 01:01:56 AM

  1. #include<stdio.h>
  2. #include<math.h>
  3. #define MAX 2703664
  4.  
  5. int prime[ MAX ] = { 0 } , divide[ MAX ] = { 0 } , *f ;
  6. int main()
  7. {
  8.         int i , j , k , n , num = 1 , tmp = (int)sqrt( MAX );
  9.         printf("%d\n", tmp*tmp*tmp);
  10.         for( i = 2 ; i<=tmp ; i++ )
  11.             for( j  = i ; !prime[ i ] && i*j < MAX ; j++ )
  12.                         for( k = i*j ; !prime[ j ] && k < MAX && k>0 ; k *= i )
  13.                         {
  14.                                 prime[ k ] = 1 ;
  15.                                 divide[ k ] = i ;
  16.                         }
  17.         f = prime ;
  18.         for( f[2] =1 , i = 3 ; i<MAX ; i++ )
  19.         {
  20.                 if( !divide[ i ] )
  21.                         f[ i ] = 1 ;
  22.                 else
  23.                     f[ i ] = f[ i/divide[ i ] ] + f[ divide[ i ] ] ;
  24.         }
  25.         f[ 0 ] = f[ 1 ] = 0 ;
  26.         for( f[ 2 ] = 1 , i = 3 ; i<MAX ; i++ )
  27.                 f[ i ] = f[ i-1 ] + f[ i ] ;
  28.         while( scanf( "%d" , &n ) && n >= 0 )
  29.         {
  30.                 printf( "Case %d:" , num++ ) ;
  31.                 for( i = 0 , j = MAX-1 , k = ( MAX-1 )/2 ;  ; k = ( i+j )/2 )
  32.                 {
  33.                         if( j<i  )
  34.                         {
  35.                                 puts( " Not possible." ) ;
  36.                                 break ;
  37.                         }
  38.                         else if( f[ k ] == n )
  39.                         {
  40.                                 if( f[ k-1 ] == n )
  41.                                         k-- ;
  42.                                 printf( " %d!\n" , k ) ;
  43.                                 break ;
  44.                         }
  45.                         else if( n>f[ k ] )
  46.                                 i = k+1 ;
  47.                         else if( n<f[ k ] )
  48.                                 j = k-1 ;
  49.                 }
  50.         }
  51.         return 0 ;
  52. }

Raw Paste


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