FPRIME

Xem PDF



Thời gian:
Python 3 7.0s
Bộ nhớ:
Python 3 512M

Tác giả:
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hôm nay, em gái của hdm học về số nguyên tố nên hdm quyết đinh ra một bài tập cho em. Đề bài như sau: Cho một số tự nhiên \(N\), kiểm tra \(N\) có phải số nguyên tố hay không. Nhưng em gái hdm lại làm xong (và đương nhiên là đúng) quá nhanh, nên hdm quyết đinh ra thật nhiều bài nữa. Hãy giúp em gái hdm giải các bài đó nhé.

Input

  • Dòng đầu ghi một số nguyên dương \(K\) là số số cần kiểm tra.
  • \(K\) dòng tiếp theo mỗi dòng ghi một số tự nhiên \(N\) là số cần kiểm tra.

Output

  • In ra \(K\) dòng, mỗi dòng là YES nếu số đó là số nguyên tố, và NO nếu không phải.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(K \lt 10^3,N \lt 10^7\).
  • Subtask \(2\) (\(80\%\) số điểm): \(K \lt 10^6,N \lt 10^7\).

Example

Test 1

Input
2
2
9 
Output
YES
NO

Bình luận


  • 0
    penistone 9:22 p.m. 11 Tháng 12, 2023 đã chỉnh sửa
    Hint

    Dùng sàng nguyên tố đến \(10^7\), nhập rồi xét nó trong sàng
    Lưu ý rằng nếu dùng endl trong c++ thì bị TLE còn nếu dùng "\n" thì lại AC
    (Phải dùng ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); thì mới không bị TLE)
    Code C++: https://ideone.com/jySYst


    • 0
      spiderman 8:13 a.m. 3 Tháng 9, 2023

      python 3 khó a quá


      • 5
        Phucc 9:02 p.m. 3 Tháng 11, 2022

        LOL, dùng "\n" thì AC còn endl thì Time Limit =))


        • 2
          VoBaThongL921 3:20 p.m. 4 Tháng 11, 2021

          bài ni mình dùng sàng nguyên tố cũng ac nha các bạn ;-;

          2 phản hồi

          • 2
            minhtuanitk20 10:41 p.m. 21 Tháng 9, 2021

            chạy sàng bool check cũng tle quái thật