FPRIME

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Pypy 3 7.0s
Python 3 7.0s
Bộ nhớ:
Pypy 3 512M
Python 3 512M
Tác giả:
Small
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
    tk22NguyenPhuongLam    6:54 p.m. 18 Tháng 4, 2024

    python nha:
    import sys
    input=sys.stdin.readline
    print=sys.stdout.write
    def sangnt():
    for p in range(2,LIMIT+1):
    if sieve[p]:
    for m in range(2p,LIMIT+1,p):
    sieve[m]=False
    LIMIT=10**7
    sieve=[True]    (LIMIT+1)
    sieve[0]=sieve[1]=False
    t=int(input())
    sangnt()
    for _ in range(t):
    n=int(input())
    if sieve[n]==True:
    print("YES\n")
    else:
    print("NO\n")

    • 7 bình luận nữa