VL11 - Kiểm tra số nguyên tố

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Cho số nguyên ~n~, hãy viết chương trình kiểm tra xem ~n~ có phải số nguyên tố hay không?

Input

Số nguyên ~n~ cần kiểm tra

Giới hạn:

  • ~|n| \le 10^{12}~

Output

Nếu ~n~ là số nguyên tố, in ra YES, ngược lại in ra NO

Sample

Input #1
7
Output #1
YES

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    huykhanh222  đã bình luận lúc 23, Tháng 3, 2025, 4:16

    include <iostream>

    include <string>

    using namespace std; bool isPrime(long long n){ if (n<2) return false; if (n==2||n==3) return true; if (n%2==0||n%3==0) return false;

    for (long long i=5;i*i<=n;i+=6){ if (n%i==0 ||n%(i+2)==0) return false; } return true; }

    int main() { long long n; cin>>n; if (isPrime(n)) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0;

    }


  • 1
    ngtuananh  đã bình luận lúc 24, Tháng 2, 2025, 7:39

    abs(n)=10^12 nhưng mà full code tui chỉ cần int cũng qua:))))


  • 2
    NC1  đã bình luận lúc 19, Tháng 1, 2025, 7:51

    Hint:

    vì abs(n) <= 10^12 nên nếu duyệt trâu sẽ TLE. Nếu ta sẽ xét từ đoạn [2; sqrt(n)]. Bổ sung thêm 2 cái if, 1 cái true với n = 2 và 3, 1 cái false cho số nhỏ hơn 3 hoặc chia hết cho 2, 3. Sau đó mới duyệt for kiểm tra các số dạng 6k ± 1 từ 5 đến căn bậc hai của n. Nếu chăm viết code thì dùng Miller - Rabin. Nhớ xử lí trường hợp số âm


  • 0
    nguyenbaongan  đã bình luận lúc 23, Tháng 12, 2024, 14:12

    case 5 là gì v mng


  • -2
    frekraiko23  đã bình luận lúc 27, Tháng 10, 2024, 6:21

    test cuối là gì vậy m.n?


  • -2
    quang_bt  đã bình luận lúc 21, Tháng 10, 2024, 11:46

    bthg thoiii


  • -2
    kietjumper  đã bình luận lúc 9, Tháng 10, 2024, 2:39

    Mình nghĩ là chỉ có ad mới xem đc test thôi 😅


  • 0
    kietjumper  đã bình luận lúc 3, Tháng 8, 2024, 15:32 chỉnh sửa

    • -3
      kietjumper  đã bình luận lúc 3, Tháng 8, 2024, 15:33

      Code tham khao nhe! c++17. Neu thay dung cho 1 up vote nhe


  • -2
    phan_phat_dat  đã bình luận lúc 11, Tháng 2, 2024, 16:03

    cái khúc if n <= 3: return True sai sai sao á

    tại sao bé hơn 2 thì sao mà bé hơn hoặc bằng 3 lại đúng


  • -2
    BienLon8888  đã bình luận lúc 17, Tháng 2, 2024, 14:40

    bạn sửa chỗ for (i=2,...) mới đúng


  • -5
    khoaphamby  đã bình luận lúc 10, Tháng 12, 2023, 11:54

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.