โจทย์
เราได้รับตัวเลข n เราต้องหาเลขเฉพาะที่ใกล้ที่สุดและน้อยกว่า n เราสามารถหาตัวเลขได้ง่ายๆ หากเริ่มตรวจสอบจาก n - 1 มาดูตัวอย่างกัน
อินพุต
10
เอาต์พุต
7
อัลกอริธึม
- กำหนดตัวเลข n
- เขียนลูปที่วนรอบจาก n - 1 ถึง 1
- คืนค่าเลขเฉพาะแรกที่เจอ
- คืนค่า -1 ถ้าไม่พบเลขเฉพาะที่น้อยกว่า n ที่กำหนด
การนำไปใช้งาน
ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน 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;
}
ผลลัพธ์
หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้
19
