Chúng ta đã cho một số n, chúng ta cần tìm số nguyên tố gần nhất nhỏ hơn n. Chúng ta có thể dễ dàng tìm thấy số nếu chúng ta bắt đầu kiểm tra từ n - 1. Hãy xem một số ví dụ.
Đầu vào
10
Đầu ra
7
Thuật toán
- Khởi tạo số n.
- Viết một vòng lặp lặp lại từ n - 1 đến 1
- Trả lại số nguyên tố đầu tiên bạn tìm thấy
- Trả về -1 nếu bạn không tìm thấy bất kỳ số nguyên tố nào nhỏ hơn n cho trước
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong C ++
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
if (n == 2) {
return true;
}
for (int i = 2; i <= ceil(sqrt(n)); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
int getNearestPrimeNumber(int n) {
for (int i = n - 1; i > 1; i--) {
if (isPrime(i)) {
return i;
}
}
return -1;
}
int main() {
int n = 20;
cout << getNearestPrimeNumber(n) << endl;
return 0;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
19