1036 . How Many Primes?

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

青い猫

User's AC Ratio

86.9% (226/260)

Submission's AC Ratio

40.0% (349/873)

Tags

number-theory

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 1

4
1
3
100
10000000

Sample Output 1

0
2
25
664579

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
Submit
Back to Top