Hướng giải của Kiểm tra số nguyên tố

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng: Duyệt từ 2 đến sqrt(N), kiểm tra N có chia hết cho số nào không. Nếu không có ước số nào thì N là số nguyên tố.

Độ phức tạp: O(√N) thời gian, O(1) bộ nhớ.

C++

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

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    cout << (isPrime(n) ? "YES" : "NO");
    return 0;
}

Python

import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.isqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

n = int(input())
print("YES" if is_prime(n) else "NO")

Nhận xét

Không có ý kiến tại thời điểm này.