TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

92.3% (84/91)

Submission's AC Ratio

39.1% (117/299)

Tags

Description

質數,就是指其正因數只有1及本身的正整數,當然一般來說我們不把1當作質數。

問題很簡單,對於一個正整數n,請問1到n之間總共有多少質數?

請你寫個程式來解決很多個這樣的問題。

Input Format

輸入檔的第一列有一個正整數m (1<=m<=100,000),代表接下來的問題個數。
接下來的m列每一列有一個正整數n (1<=n<=10,000,000)。

Output Format

對每一組測試資料請你輸出1與n之間的質數個數。

Sample Input

4
1
3
100
10000000

Sample Output

0
2
25
664579

Hints

Problem Source

原TIOJ1036 / 經典問題練習, Problem Setter: Tmt

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536