Problems
에라토스테네스의 체는 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으로 바뀌는 배열의 번호) 프로그램을 구현하라.
Input
입력은 한줄로 이뤄지며 정수 N이 주어진다. N은 4이상 2,000,000,000이하의 정수다.
Output
입력에 대해 마지막으로 실행되는 x*y의 값을 출력한다.
Example
18
15
Hint
You must sign in to write code.