CPP   22

prime divide

Guest on 30th June 2022 02:45:20 AM

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

Raw Paste

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