ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมที่ตรวจสอบว่าตัวเลขที่ระบุเป็น k-rough หรือไม่ หรือ k-jagged จำนวนหรือไม่
จำนวนที่มีตัวประกอบเฉพาะน้อยที่สุดมากกว่าหรือเท่ากับ k ที่กำหนด เรียกว่า k-rough หรือ k-jagged เลขที่
มาดูขั้นตอนการแก้ปัญหากัน
- เริ่มต้นตัวเลข n และ k .
- หาจำนวนเฉพาะที่เป็นตัวประกอบของ n และเก็บไว้ในเวกเตอร์
- รับองค์ประกอบแรกจากเวกเตอร์แล้วเปรียบเทียบกับ k เพื่อตรวจสอบว่า n คือ k-rough หรือ k-jagged จำนวนหรือไม่
ตัวอย่าง
มาดูโค้ดกันเลย
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
vector<int> getPrimes(int n) {
vector<int> primes;
for (int i = 2; i < n; i++) {
if (n % i == 0 && isPrime(i)) {
primes.push_back(i);
}
}
return primes;
}
bool isRoughNumber(int n, int k) {
vector<int> primes = getPrimes(n);
return primes[0] >= k;
}
int main() {
int n = 75, k = 3;
if (isRoughNumber(n, k)) {
cout << n << " is a " << k << " rough number" << endl;
}else {
cout << n << " is not a " << k << " rough number" << endl;
}
return 0;
} ผลลัพธ์
หากคุณเรียกใช้โปรแกรมข้างต้น คุณจะได้ผลลัพธ์ดังต่อไปนี้
75 is a 3 rough number
บทสรุป
คุณสามารถหลีกเลี่ยงการเก็บจำนวนเฉพาะทั้งหมดในเวกเตอร์ได้ และหาตัวประกอบเฉพาะตัวแรกของ n และเปรียบเทียบกับ k เพื่อให้ได้ผลลัพธ์ที่ต้องการ นำแนวคิดที่คล้ายกับแนวคิดข้างต้นมาใช้โดยมีพื้นที่และเวลาน้อยกว่า
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
