Follows 10015.c (Total 67 lines):

/* @JUDGE_ID:4461XX 10015 C "simulation" */
/* A */
#include<stdio.h>
#include<string.h>
#define MAX 3501
#define PRI 32610 /* the 3500th prime number is 32609 */

typedef struct{
	int from ;
	int index ;
	int next ;
	int dead ;
}JosephArray ;

JosephArray a[MAX] ;
int pri[MAX-1] ;

void make_primetable( void )
{
	int i , j , tail , prime[PRI] ;

	for( i=0 ; i<PRI ; i++ ) prime[i] = 1 ; /* initial */
	for( tail=-1,i=2 ; i<PRI ; i++ )
		if( prime[i] ){
			pri[++tail] = i ;
			for( j=2 ; i*j<PRI ; j++ ) prime[i*j] = 0 ;
		}
}
int count( int people )
{
	int i , j , p ;

	for( i=0 ; i<people ; i++ ){ /* initial */
		a[i].from = i-1 ;
		a[i].index = i+1 ;
		a[i].next = i+1 ;
		a[i].dead = 0 ;
	}
	a[0].from = people-1 ;
	a[people-1].next = 0 ;

	for( p=0,i=0 ; i<people-1 ; i++ ){
		for( j=1 ; j<pri[i] ; j++ ) p = a[p].next ;

		a[p].dead = 1 ; /* killed */
		a[ a[p].from ].next = a[p].next ;
		a[ a[p].next ].from = a[p].from ;
		p = a[p].next ;
	}

	for( i=0 ; i<people ; i++ ) /* find one who is alive */
		if( !a[i].dead ) return a[i].index ;
}
int main( void )
{
	int n ;
	
	make_primetable() ;
	while( scanf( "%d" , &n )==1 ){
		if( !n ) break ;

		printf( "%d\n" , count( n ) ) ;
	}

	return 0 ;
}
/* @END_OF_SOURCE_CODE */

Back to statistics
Ya-Lin Huang (C)
huangyl@gmail.com