Đếm số nguyên tố trong khoảng trong C++

Cho các biến phạm vi START và END. Mục tiêu là tìm số lượng số nguyên tố trong khoảng [START, END].

Ta kiểm tra số i trong khoảng có phải nguyên tố bằng cách kiểm tra xem có số nào khác 1 chia hết nó và nằm giữa 1 và i/2 không. Nếu là nguyên tố thì tăng biến đếm.

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

Đầu vào

Start=1 End=20

Đầu ra

Số nguyên tố trong khoảng: 8

Giải thích

Các số nguyên tố giữa 1 và 20: 2,3,5,7,11,13,17,19.

Đầu vào

Start=100 End=200

Đầu ra

Số nguyên tố trong khoảng: 21

Giải thích

Các số nguyên tố giữa 100 và 200: 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

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

• Nhận biến phạm vi START và END.
• Hàm countPrimes(int strt, int end) trả về số lượng số nguyên tố trong khoảng.
• Khởi tạo biến count = 0.
• Duyệt bằng vòng lặp for từ i=strt đến i <= end.
• Lấy từng số i và kiểm tra nguyên tố bằng hàm isprime(i).
• Hàm isprime(int num) trả về 0 nếu không phải nguyên tố, 1 nếu là nguyên tố.
• Sau vòng lặp trả về count làm kết quả.

Ví dụ

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

int isprime(int num) {
    if (num <= 1) return 0;
    for (int i = 2; i <= num/2; i++) {
        if (num % i == 0) return 0;
    }
    return 1; // nếu cả hai thất bại thì num là nguyên tố
}

int countPrimes(int strt, int end) {
    int count = 0;
    for(int i = strt; i <= end; i++) {
        if(isprime(i) == 1) {
            count++;
        }
    }
    return count;
}

int main() {
    int START = 10, END = 20;
    cout << endl << "Số nguyên tố trong khoảng: " << countPrimes(START, END);
    return 0;
}

Đầu ra

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

Số nguyên tố trong khoảng: 4