1251 . 幸運數
TopCoder
Tags
Description
『幸運數』是在1955年波蘭數學家烏拉姆提出，它其實是一串藉由特定規則而得的正整數數列。要如何得到一串幸運數列呢？
我們先列出正整數數列：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25...
接著刪去所有的偶數，剩下奇數數列：
1 3 5 7 9 11 13 15 17 19 21 23 25...
數列的第2個數為3，故從頭開始3個一數將數字刪去：
1 3 7 9 13 15 19 21 25...
數列的第3個數為7，故從頭開始7個一數將數字刪去：
1 3 7 9 13 15 21 25...
重複以上的過程，最後留下來的數字便形成幸運數列：
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99 ...
皮皮最近正不斷累積TIOJ的Accepted，因為皮皮對解題極度有把握，他絕不會有卡關的問題。
經過一段時間，他發現他預定要寫到的題數—193，竟然也是幸運數（數列第38個）！於是他對幸運數便有了極大的好奇心，希望Lucky Number可以帶給他極大的破題功力。不過皮皮對第N個數是哪個幸運數的問法毫無興趣，此刻他最想知道的是：輸入一個數字N，請問1到N之間存在多少個幸運數？
Input Format
輸入可能包含多筆測試資料。
每筆測試資料有一個正整數N（1 ≦ N ≦ 1000000）。
當N = 0時，代表輸入結束，聰明的你當然不會對它輸出任何資料。
Output Format
請輸出一個整數，表示1到N間有多少個幸運數。
Sample Input 1
5
24
25
0
Sample Output 1
2
7
8
Hints
（皮皮補註：這題絕對不是我出的= =）
Problem Source
原TIOJ1251 / INFOR 21st幹部考(prob G)。Problem Setter：peter50216。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |