알고리즘을 좋아하는 나

1^14 의 square root 는 1^7이다.

1^7까지의 소수만 구해주면 된다.

그래서 2~1^7까지의 소수를 구하고, 

primeNumber에 소수들을 넣어준다.

primeNumber에 들어간 소수들로 

max => n * primeNumber[i]를 계산해준다.

여기서 주의해야 될 점이 n이 long long을 넘어가는 경우다.

하지만 이항을 해서

max / n >= primeNumber[i]로 변경할 수 있다.

그리고 min >=의 경우를 구해야줘야 되는데, 이미 while loop에서 체크를 해줘서 밑에서는 체크를 안해줘도 된다.

에라토스테네스의 체를 이용해서 소수들을 구하고

시간복잡도를 줄여주기 위해

i -= 2 를 해줬다.

그리고 for loop을 2개 중첩안시킴

에라토스테네스의 체의 방법을 사용하는데, 소수를 구하는게 목적이 아니고 K 번째 지워지는 숫자를 구하는게 목적

아이디어 :

1. 에라토스테네스의 체를 이용해서 소수를 구한다.

2. 소수를 primeNumber에 하나씩 넣어준다. 마지막값은 0이다.

3. 2... 돌게되면 0이 나오는데 0이면 반복문을 종료한다.

4. 반복문 안에 반복문을 넣어서 값을 더해주고 맞으면 빼기한 값을 저장하고 그걸로 체크를한다.

더 좋은 방법.

어차피 빼기값을 최소로 구하는거니까. n/2부터 시작해서 하나씩 빼면서 맞는답이 나오면 바로 출력하면 더 빠르다.

이 방법을 사용하면 2번 과정이 없어진다.

더 좋은 방법을 사용한다면,

O(Nnlgn)이 될거같다.

문제를 딱 보고.

아 이건! 미리 구해놓고 하나씩 출력하면 될듯~

에라토스테네스의 체를 복습했다.