Đếm tất cả các số nhỏ hơn 10 ^ 6 có thừa số nguyên tố nhỏ nhất là N C ++

Chúng ta được cho một số nguyên tố, giả sử là num và nhiệm vụ là tính tổng số tất cả các số nhỏ hơn 10 ^ 6 có hệ số nguyên tố nhỏ nhất bằng num.

Ví dụ

Input − num = 7
Output − Number of prime factors = 38095

Input − num = 3
Output − Number of prime factors = 16666

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Nhập số, giả sử là num

• Bắt đầu vòng lặp, từ i đến 2 và i phải nhỏ hơn hoặc bằng giá trị lớn nhất và tăng giá trị của i

• Trong vòng lặp, hãy kiểm tra xem s_prime [i] =0

• Tạo vòng lặp, đặt j thành i * 2 và j phải nhỏ hơn bằng thành max và đặt j thành j + i

• Bây giờ hãy kiểm tra, nếu s_prime [j] =1

• Đặt s_prime [j] =1

• Tăng s_count [i] lên 1

• In kết quả

Ví dụ

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
// a sieve for prime number and
// to count the number of prime
int s_prime[MAX + 4] = { 0 }, s_count[MAX + 4] = { 0 };
void create_sieve(){
   // As 1 is not a prime number
   s_prime[1] = 1;
   // creating the sieve
   for (int i = 2; i <= MAX; i++){
      // if i is a prime number
      if (s_prime[i] == 0){
         for (int j = i * 2; j <= MAX; j += i){
            // if i is the least prime factor
            if (s_prime[j] == 0){
               // The number j is not a prime
               s_prime[j] = 1;
               // counting the numbers whose least prime factor
               // is i
               s_count[i]++;
            }
         }
      }
   }
}
int main(){
   // create the sieve
   create_sieve();
   int N = 7;
   cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
   N = 3;
   cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
   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 -

Number of prime factors = 38095
Number of prime factors = 166667