Follows 10140.c (Total 77 lines):
/* @JUDGE_ID:4461XX 10140 C */
/* A */
#include<stdio.h>
#include<limits.h>
#include<math.h>
#define MAX 4792 /* numbers of prime <46340 are 4792 */
int max[3] , min[3] ; /* 0->dis , 1->c1 , 2->c2 */
int prime[MAX] ; /* the i'th prime is prime[i] */
int from , to ;
void MakePrime( void )
{
char tmp[46340] ; /* sqrt( 2^31-1 ) */
int i , j , point ;
for( i=0 ; i<46340 ; ++i ) tmp[i] = 1 ;
for( point=0,i=2 ; i<46340 ; ++i )
if( tmp[i] ){
prime[point++] = i ;
for( j=2 ; i*j<46340 ; ++j ) tmp[i*j] = 0 ;
}
}
void ToDo( void )
{
int array[1000000] ;
int i , j ;
for( i=0 ; i<=to-from ; ++i ) array[i] = 1 ;
if( from==1 ) array[0] = 0 ;
for( i=0 ; i<MAX ; ++i ){
for( j=( (int)ceil( (double)from/(double)prime[i] )<=1?2:(int)ceil( (double)from/(double)prime[i] ) ); j<=to/prime[i] ; ++j ){
array[ prime[i]*j-from ] = 0 ;
}
}
max[0] = INT_MIN ;
min[0] = INT_MAX ;
for( j=0 ; !array[j] ; ++j ) ;
for( i=j+1 ; i<=to-from ; ++i )
if( array[i] ){
if( i-j>max[0] ){
max[0] = i-j ;
max[1] = j+from ;
max[2] = i+from ;
}
if( i-j<min[0] ){
min[0] = i-j ;
min[1] = j+from ;
min[2] = i+from ;
}
j = i ;
}
}
void Print( void )
{
if( max[0]==INT_MIN || min[0]==INT_MAX )
puts( "There are no adjacent primes." ) ;
else
printf( "%d,%d are closest, %d,%d are most distant.\n" ,
min[1] , min[2] , max[1] , max[2] ) ;
}
int main( void )
{
MakePrime() ;
while( scanf( "%d %d" , &from , &to )==2 ){
ToDo() ;
Print() ;
}
return 0 ;
}
/* @END_OF_SOURCE_CODE */
Back to statistics
Ya-Lin Huang (C)
huangyl@gmail.com