649 . 質數判斷 2

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

80.0% (4/5)

Tags

apcsc apcsc-timecomplexity

Description

迷上搜集質數的學姐收到了你給她能回答「一個正整數是不是質數」的程式後很開心，開始頻繁的使用他，但學姐用久了便發現這支程式回答所花的時間有點久，就算他能夠回答到大至 1010 的數字，學姐也不需要問到這麼大的數字。因此，學姐降低了詢問的數字範圍，並希望你能再寫一支程式更快速的回答她的問題。

Input Format

輸入第一行有一個正整數 T ，代表學姐的問題數量。接下來 T 行，每一行都是一個學姐的提問，第 i 行包含一個正整數 Xi ，代表第 i 個問題是 Xi 是不是質數。

  • 1≤T≤106
  • 1≤Xi≤106

Output Format

輸出有 T 行，每一行都是 YES 或 NO，代表那次詢問的正整數是不是質數。

Sample Input 1

7
3
4
5
6
7
8
999967

Sample Output 1

YES
NO
YES
NO
YES
NO
NO

Hints

Problem Source

Subtasks

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

Testdata and Limits

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