C Bài 4.E1: 2 thừa số nguyên tố

Submit solution
Points: 30 (partial)
Time limit: 1.0s
Memory limit: 20M
Author:
buitrunghieu
Problem type

Cho số nguyên dương \(a\). Hãy kiểm tra xem số \(a\) có đúng 2 loại thừa số nguyên tố không. Ví dụ như số 8 có 1 loại thừa số nguyên tố là 2, trong khi 14 có 2 loại là 2 và 7.

INPUT FORMAT

Dòng đầu tiên là số nguyên \(q\) biểu thị số truy vấn \((1 \leq q \leq 20)\).

\(Q\) dòng tiếp theo, mỗi dòng gồm 1 số nguyên dương \(a (1 \leq a \leq 10^5)\).

OUTPUT FORMAT

In ra \(q\) dòng, mỗi dòng in ra YES nếu \(a\) thỏa mãn yêu cầu đề bài, ngược lại in ra NO.

Ví dụ:

Input
3
2
6
9
Output
NO
YES
NO
Giải thích ví dụ mẫu:
  • Ví dụ 1: Số 2 có 1 loại thừa số nguyên tố, không đáp ứng yêu cầu.
  • Ví dụ 2: Số 6 có 2 loại thừa số nguyên tố (2 và 3), đáp ứng yêu cầu.
  • Ví dụ 3: Số 9 có 1 loại thừa số nguyên tố, không đáp ứng yêu cầu.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House

Comments


  • 0
    endc67_fullhouse_dev  commented on Jan. 5, 2025, 7:31 a.m. 
    #include <bits/stdc++.h>
using namespace std;

// Hàm kiểm tra xem số nguyên a có đúng 2 loại thừa số nguyên tố không
bool hasTwoDistinctPrimeFactors(int a) {
    int primeCount = 0;

    // Kiểm tra thừa số 2
    if (a % 2 == 0) {
        primeCount++;
        while (a % 2 == 0) {
            a /= 2;
        }
    }

    // Kiểm tra các số lẻ từ 3 đến sqrt(a)
    for (int i = 3; i * i <= a; i += 2) {
        if (a % i == 0) {
            primeCount++;
            while (a % i == 0) {
                a /= i;
            }
        }
        if (primeCount > 2) return false; // Nếu có hơn 2 loại thừa số nguyên tố thì trả về false
    }

    // Nếu a > 1, có một thừa số nguyên tố còn lại
    if (a > 1) primeCount++;

    return primeCount == 2; // Kiểm tra có đúng 2 loại thừa số nguyên tố không
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    while (q--) {
        int a;
        cin >> a;
        if (hasTwoDistinctPrimeFactors(a)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}
// Luoi lam nen dung chatgpt
Zalo