KT Số nguyên tố

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 900 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Trong ngày thực tập đầu tiên, thầy Hải 'dới' có một câu đố nho nhỏ cho các học sinh của mình. Cho một số nguyên \(n\), hãy kiểm tra \(n\) có phải là số nguyên tố hay không?

Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có hai ước số dương phân biệt là 1 và chính nó.

Input:

  • Gồm một dòng duy nhất là số nguyên \(n (|n| \le 10^{12})\)

Output:

  • In ra YES nếu \(n\) là số nguyên tố. Ngược lại in ra NO.

Example

Test 1

Input 
9
Output 
NO

Test 1

Input 
7
Output 
YES

Bình luận

  • ronaldo12345 • 10:47 a.m. 23 Tháng 12, 2024 • ← đã chỉnh sửa 

    #include <iostream>
#include <cmath>
using namespace std;

bool snt(int n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i <= sqrt(n); i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}
int main() {
    long long n;
    cin >> n;

    if (snt(n)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

    Giải thích:
    Trường hợp đặc biệt:

    Các số nhỏ hơn 2 không phải số nguyên tố.
    Số 2 và 3 là số nguyên tố.
    Loại bỏ nhanh:

    Nếu số chia hết cho 2 hoặc 3, nó không phải là số nguyên tố.
    Kiểm tra với các số lớn hơn:

    Chỉ cần kiểm tra đến căn bậc hai của số đó vì nếu n chia hết cho một số lớn hơn căn bậc hai của nó, thì sẽ tồn tại một số nhỏ hơn căn bậc hai cũng chia hết.
    Bước nhảy 6 được sử dụng để kiểm tra các số dạng 6k ± 1 vì các số khác đã bị loại bỏ (chia hết cho 2 hoặc 3).

    0
    Phản hồi
      • 21 bình luận nữa