Đếm số nguyên tố trong phạm vi trong C ++

Chúng tôi được cung cấp các biến phạm vi START và END. Mục đích là để tìm số lượng các số nguyên tố trong phạm vi [START, END].

Chúng tôi sẽ kiểm tra xem số i trong phạm vi có phải là số nguyên tố hay không bằng cách kiểm tra xem có số nào khác 1 chia hết cho nó và nằm trong khoảng từ 1 đến i / 2 hay không. Nếu nó là số nguyên tố. Số lượng tăng dần.

Hãy cùng hiểu với các ví dụ.

Đầu vào

Start=1 End=20

Đầu ra

Primes in Ranges : 8

Giải thích

Primes between 1 and 20 are: 2,3,5,7,11,13,17,19.

Đầu vào

Start=100 End=200

Đầu ra

Primes in Ranges : 21

Giải thích

Primes between 100 and 200 are: 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 tiếp cận được sử dụng trong chương trình dưới đây như sau

• Chúng tôi lấy các biến phạm vi là START và END.

• Hàm countPrimes (int strt, int end) trả về số lượng các số nguyên tố trong phạm vi.

• Lấy số lượng biến ban đầu là 0.

• Di chuyển bằng vòng lặp for từ i =strt đến i <=end

• Lấy từng số i và kiểm tra xem nó có phải là số nguyên tố hay không bằng cách sử dụng isprime (i).

• Hàm isprime (int num) trả về 0 nếu số không phải là số nguyên tố và 1 nếu là số nguyên tố.

• Sau khi kết thúc vòng lặp, trả về số lượng là 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; //if both failed then num is prime
}
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<<"Primes in Ranges : "<<countPrimes(START,END);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Primes in Ranges : 4