1045 - 상대 소수

• Submit
• Status
• Discuss
• Summary

Description

자연수 n이 주어졌을 때, ① n보다 미만이면서, ② n에 대해 상대 소수인 자연수의 개수는 몇개일까요?

2개의 자연수 a,b가 1외에 공통의 약수를 가지지 않을 때 이들을 서로에 대한 상대소수라고 합니다. (다른 말로, x > 1, y >0, z >0 일때 a=xy, b=xz인 x,y,z가 없음)

Input

* Line 1 ~ N : 단일 상수 n (입력 값, 최대 1,000,000,000)

* Line 1+N : 단일 상수 0 (문제 입력의 끝을 나타냄)

Output

* Line 1 ~ N : 상대 소수의 개수

Sample Input

7
12
0

Sample Output

6
4

Hint

예를 들어, 7의 상대소수는 1,2,3,4,5,6 입니다.

 

12일때에는 1,5,7,11이 되겠죠!