에라토스테네스의 체는 2이상 N이하의 모든 소수를 찾는 오래된 방법이다.

다음은 C로 구현한 에라토스테네스의 체의 코드이다.

int isprime[NN+1], x, y; // NN은 N보다 큰 임의의 정수다. for(x=2; x<=N; ++x) isprime[x] = 1; for(x=2; x<=N; ++x) { if( isprime[x] == 1 ) { for(y=2; y<=N/x; ++y) { if( isprime[x*y] ) { isprime[x*y] = 0; } } } }

위의 코드를 구동시킬 경우 isprime[x] 는 x가 소수일 경우 1, 아닐 경우 0이 된다.

N이 주어졌을 때 위의 코드의 8번째 줄이 실행될 때 마지막으로 실행되는 x*y의 값을 찾는(마지막으로 0으로 바뀌는 배열의 번호) 프로그램을 구현하라.

#2410 upload 18 done 11 how_to_reg 8

에라토스테네스의 체 timer 1s memory - MB

#2410

에라토스테네스의 체 1s - MB