최소 소인수가 N인 10^6보다 작은 모든 숫자를 센다 C++

우리에게 num이라는 소수가 주어지고 최소 소인수가 num과 같은 10^6보다 작은 모든 숫자의 개수를 계산하는 것이 작업입니다.

예

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

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

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

• 숫자를 입력하세요. 예를 들어 num

• i에서 2까지 루프를 시작하고 i는 최대값보다 작거나 같아야 하고 i

  의 값을 증가시켜야 합니다.

• 루프 내에서 s_prime[i] =0

  인지 확인하십시오.

• 루프를 만들고 j를 i * 2로 설정하고 j는 max보다 작아야 하고 j를 j + i로 설정

• 이제 s_prime[j] =1

  인지 확인합니다.

• s_prime[j] =1로 설정

• s_count[i]를 1 증가

• 결과 인쇄

예시

#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;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

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