Số K-Rough hoặc K-Jagged trong C++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình kiểm tra xem số cho trước có phải là K-rough hay K-jagged hay không.

Số có ước nguyên tố nhỏ nhất lớn hơn hoặc bằng K được gọi là K-rough hoặc K-jagged.

Các bước giải quyết

• Khởi tạo số N và K.
• Tìm tất cả ước nguyên tố của N lưu vào vector.
• Lấy phần tử đầu tiên so sánh với K để kiểm tra.

Ví dụ

Dưới đây là mã nguồn C++:

#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; 
}

Kết quả

Nếu bạn chạy chương trình trên, kết quả sẽ là:

75 is a 3 rough number

Kết luận

Bạn có thể tránh lưu tất cả ước nguyên tố. Chỉ tìm ước nguyên tố đầu tiên của N và so sánh với K để tối ưu không gian và thời gian.

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.