173 . 全部成為 F

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

50.0% (9/18)

Tags

ioicamp ioicamp-2022

Description

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

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

Input Format

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

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

  • $1 \leq Q \leq 10^ 6$
  • $1 \leq N \leq 10^ 6$

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
Submit
Back to Top