1719 測資加強 已 rejudge
1036 . How Many Primes?
TopCoder
Tags
Description
質數，就是指其正因數只有$1$及本身的正整數，當然一般來說我們不把$1$當作質數。
問題很簡單，對於一個正整數 $n$ ，請問 $1$ 到 $n$ 之間總共有多少質數？
請你寫個程式來解決很多個這樣的問題。
Input Format
輸入檔的第一列有一個正整數 $m$ ($1 \leq m \leq100,000$)，代表接下來的問題個數。
接下來的m列每一列有一個正整數 $n$ ($1\leq n \leq 10,000,000$)。
Output Format
對每一組測試資料請你輸出$1$與$n$之間的質數個數。
Sample Input 1
4
1
3
100
10000000
1
3
100
10000000
Sample Output 1
0
2
25
664579
2
25
664579
Hints
Problem Source
原TIOJ1036 / 經典問題練習, Problem Setter: Tmt
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |