EKG 수열 1초 128MB
문제
EKG 수열이란 다음과 같은 규칙을 만족하는 양의 정수들이 중복되지 않게 이루어져 있는 수열이다.
처음 두개의 항은 1과 2이다. EKG[n] 은 'EKG[n-1]과 1보다 큰 공약수를 갖는 자연수 중 지금까지 나오지 않은 가장 작은 자연수'이다.
그러므로 세번째 항은 4이고 그 다음 항은 6이다.
그리고 다음에는 3이 나오게 된다.
따라서 수열은 다음과 같이 완성된다.
1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27 ...
이 수열은 불규칙적인거 가진 것 처럼 보이지만 두 가지의 특징을 가지고 있다.
하나는 모든 자연수가 이 수열에 포함된다는 것이고 다른 하나는 모든 소수(prime number)는 오름차순으로 존재한다라는 것이다.
우리가 해야 할 것은 어떤 자연수 n이 주어졌을 때, n이 EKG 수열에서 몇 번째로 나타나는지를 구하는 것이다.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1≤T≤300,000)
다음 T줄에 걸쳐 자연수 n이 주어진다 (1≤n≤300,000).
* 300,000 이하의 숫자가 EKG 수열의 1,000,000번째 항 이후에 존재하는 경우는 없다고 가정한다.
출력
테스트 케이스 줄마다 n이 EKG 수열에서 몇 번째에 위치하는지를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 1점 | n≤10 |
| #2 | 9점 | n≤100 |
| #3 | 20점 | n≤3000 |
| #4 | 70점 | 추가 제약 조건 없음 |
예제
3
3
9
12
5
6
7
로그인해야 코드를 작성할 수 있어요.