TopCoder

Caido
主唱太拼命了

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

50.0% (9/18)

Tags

Description

7 是孤獨的,B 和 D 也是。 ——真賀田四季

對一個正整數 N ,定義 xN 以下是孤獨的,若且惟若 xN 以下的正整數中恰有一個真因數,且只有一個倍數(自己)。 請回答在 N 以下有多少孤獨的數。

Input Format

輸入的第一行有一個正整數 Q 代表接下來有幾次詢問。

接下來的 Q 行每行有一個正整數 N ,代表要求在 N 以下有多少孤獨的數。

  • 1Q106
  • 1N106

Output Format

輸出 Q 行,每行一個數字,第 i 行是第 i 次詢問的答案。

Sample Input 1

2
10
15

Sample Output 1

1
2

Hints

真因數:真因數是指一個自然數除自身以外的因數

Problem Source

IOICamp 2022 Day3 pE

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~3 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2