Đếm số trong khoảng chỉ có thừa số nguyên tố 2 và 3 trong C++

Cho hai số START và END xác định một khoảng số. Mục tiêu là tìm các số chỉ có 2 và 3 là thừa số nguyên tố của chúng và nằm trong khoảng [START, END].

Ta thực hiện bằng cách duyệt số từ START đến END và với mỗi số kiểm tra xem số đó có chia hết cho 2 và 3 chỉ. Nếu chia hết, chia và giảm số đó. Nếu không, thoát vòng lặp. Cuối cùng nếu số giảm về 1 thì nó chỉ có 2 và 3 là thừa số.

Hãy hiểu qua các ví dụ.

Đầu vào

START=20 END=25

Đầu ra

Số chỉ có thừa số 2 và 3: 1

Giải thích

Thừa số nguyên tố từng số: 20=2×2×5, 21=3×7, 22=2×11, 23=1×23, 24=2×2×2×3, 25=5×5. Chỉ 24 có thừa số 2 và 3.

Đầu vào

START=1000 END=1500

Đầu ra

Số chỉ có thừa số 2 và 3: 4

Giải thích

1024, 1152, 1296, 1458 là các số chỉ có thừa số 2 và 3.

Phương pháp sử dụng trong chương trình dưới đây

• Nhận số nguyên START và END làm biến phạm vi.
• Hàm twothreeFactors(int start, int end) nhận biến phạm vi và trả về số lượng số chỉ có 2 và 3 là thừa số nguyên tố.
• Khởi tạo biến count = 0 cho các số như vậy.
• Duyệt khoảng số bằng vòng lặp for. i=start đến i=end.
• Với mỗi số num=i, dùng vòng lặp while kiểm tra nếu num%2==0, chia nó.
• Nếu num%3==0, chia nó. Nếu không chia hết cho cả hai thì thoát while.
• Nếu sau vòng while num bằng 1 thì tăng count.
• Sau tất cả vòng lặp count chứa tổng số chỉ có 2 và 3 là thừa số nguyên tố.
• Trả về count làm kết quả.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int twothreeFactors(int start, int end) {
    // Bắt đầu từ 2 để 1 không bị đếm
    if (start == 1) {
        start++;
    }
    int count = 0;
    for (int i = start; i <= end; i++) {
        int num = i;
        while(num > 1) {
            // nếu chia hết cho 2, chia cho 2
            if(num % 2 == 0) {
                num /= 2;
            }
            // nếu chia hết cho 3, chia cho 3
            else if (num % 3 == 0) {
                num /= 3;
            }
            // nếu không chia hết cho 2 và 3 thì thoát
            else {
                break;
            }
        }
        // nghĩa là chỉ 2 và 3 là thừa số của num
        if (num == 1) {
            count++;
        }
    }
    return count;
}

int main() {
    int START = 10, END = 20;
    cout << "Số chỉ có thừa số 2 và 3: " << twothreeFactors(START, END);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số chỉ có thừa số 2 và 3: 3