EKG 수열
시간 제한1초메모리 제한128 MB
EKG 수열을 1000000번째 항까지 만들고, 각 질의 정수 n이 처음 나타나는 위치를 1부터 세어 출력한다.
문제
EKG 수열은 다음과 같이 만들어지는 양의 정수 수열이다. 수열의 처음 두 항은 1과 2이다. 그 이후의 각 항은, 아직 사용되지 않은 양의 정수 중에서 바로 앞 항과 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
이 수열은 값이 매우 불규칙하게 오르내리기 때문에 EKG(심전도)라는 이름이 붙었다. 이 수열에는 자명하지 않지만 흥미로운 성질이 몇 가지 있다. 하나는 모든 양의 정수가 언젠가 반드시 수열에 나타난다는 것이고, 다른 하나는 모든 소수가 증가하는 순서로 나타난다는 것이다. 주어진 정수가 이 수열에서 몇 번째 위치에 나타나는지 구하여라.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 하나의 정수 ()이 적힌 한 줄이다. 마지막 테스트 케이스 뒤에는 0이 입력된다. 300,000 이하의 모든 정수를 포함하는 EKG 수열의 앞부분에는 1,000,000보다 큰 정수가 나타나지 않는다.
출력
각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.
The number n appears in location p.
여기서 은 주어진 수이고 는 그 수가 EKG 수열에서 나타나는 위치이다. 는 1,000,000을 넘지 않음이 보장된다.