問題
1부터 N까지 번호가 쓰여진 N장의 카드가 왼쪽부터 오른쪽으로 순서대로 나열되어 있다.
처음에는 모든 카드가 뒷면이 위를 향한 상태로 놓여있는데, 게임이 시작되면 이 카드들은 아래 규칙에 따라 반복하여 뒤집힌다.
for k in range(2, N+1):
for i in range(k, N+1, k):
카드 i를 뒤집는다.
아래 그림은 N=6의 경우이다. 게임이 끝나면 카드 1,4는 뒷면이 위를 향하고, 나머지 카드는 앞면이 위를 향하게 된다.
<부분문제>
1. N ≤ 1,000 (10점)
2. 추가 제한 없음 (90점)
入力
첫 줄에 정수 N이 입력된다. (2 ≤ N ≤ 100,000,000)
出力
게임이 끝났을 때 앞면이 위를 향하는 카드의 개수를 출력하시오.
例題 #1
6
4
例題 #2
260015629
259999504
出典
klee
ログインしないとコードを書けません。