Số nguyên tố lớn nhất nhỏ hơn N C++

Tìm số nguyên tố lớn nhất nhỏ hơn N.

Thuật toán

• Duyệt giảm từ N-1 xuống 2.
• Kiểm tra nguyên tố (thử chia đến √n).
• Trả về số đầu tiên tìm thấy.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

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

int nearestPrimeLessThan(int n) {
    for (int i = n - 1; i >= 2; i--)
        if (isPrime(i)) return i;
    return -1;
}

int main() {
    cout << nearestPrimeLessThan(20) << endl; // 19
    return 0;
}

Kết quả

19