Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 소수의 개수와의 차이가> =K인 개수 개수 <=N

<시간/>

두 개의 정수 N과 K가 주어지면 목표는 다음 조건을 따르는 숫자의 개수를 찾는 것입니다 -

  • 번호<=N

  • | 숫자-카운트 |>=K 여기서 count는 Number보다 작거나 같은 소수의 수입니다.

예를 들어

입력

N = 5, K = 2

출력

Count of numbers < = N whose difference with the count of primes upto them is > = K are: 2

설명

The numbers that follow the conditions are:
5 ( 5−2>=2 ) and 4 ( 4−2>=2 )

입력

N = 10, K = 6

출력

Count of numbers < = N whose difference with the count of primes upto them
is > = K are: 1

설명

The numbers that follow the conditions are:
10 ( 10−4>=6 )

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

이 접근법에서 우리는 계산을 줄이기 위해 이진 검색을 사용할 것입니다. num까지의 소수의 개수가 count1이고 숫자 num+1의 경우 이 개수는 count2입니다. 그런 다음 차이 num+1−count2>=num−count1입니다. 따라서 num이 유효하면 num+1도 유효합니다. 처음 발견된 숫자에 대해 조건을 따르는 이진 검색을 사용하여 'num'이라고 말하면 'num'+1도 동일한 조건을 따릅니다. 이런 식으로 num에서 N 사이의 모든 숫자가 계산됩니다.

  • 변수 N과 K를 입력으로 사용합니다.

  • 배열 arr[]는 i까지의 소수 개수를 저장하는 데 사용되며 인덱스 i에 저장됩니다.

  • 함수 set_prime()는 소수의 개수를 저장하기 위해 배열 arr[]를 업데이트합니다.

  • 배열 검사[i]는 i가 소수이면 true를 저장하고 그렇지 않으면 false를 저장합니다.

  • 소수가 아니므로 check[0]=check[1] =false로 설정합니다.

  • 인덱스 i=2에서 i*i까지 모든 검사[j]를 0으로 설정합니다.

  • 이제 for 루프를 사용하여 arr[]을 탐색하고 업데이트합니다. 모든 카운트는 최대 arr[i]=arr[i−1]입니다. arr[i] 자체가 소수이면 해당 개수는 1만큼 증가합니다. arr[i]++를 설정합니다.

  • 함수 total(int N, int K)는 N과 K를 취하여 소수의 개수와의 차이가> =K인 숫자의 개수 <=N을 반환합니다.

  • set_prime()를 호출합니다.

  • temp_1=1 및 temp_2=N을 선택합니다. 초기 카운트를 0으로 합니다.

  • 이제 이진 검색을 사용하여 while 루프에서 set =(temp_1 + temp_2)>> 1 ((first+last) /2 ).

  • set−arr[set]이>=K이면 조건이 충족되고 set과 temp_2=set−1로 count를 업데이트합니다.

  • 그렇지 않으면 temp_1=temp_1+1로 설정합니다.

  • 마지막에 카운트를 최소 유효 숫자 N−count+1 또는 0으로 설정합니다.

  • 모든 루프가 끝나면 count를 결과로 반환합니다.

예시

#include <bits/stdc++.h>
using namespace std;
#define size 1000001
int arr[size];
void set_prime(){
   bool check[size];
   memset(check, 1, sizeof(check));
   check[0] = 0;
   check[1] = 0;
   for (int i = 2; i * i < size; i++){
      if(check[i] == 1){
         for (int j = i * 2; j < size; j += i){
            check[j] = 0;
         }
      }
   }
   for (int i = 1; i < size; i++){
      arr[i] = arr[i − 1];
      if(check[i] == 1){
         arr[i]++;
      }
   }
}
int total(int N, int K){
   set_prime();
   int temp_1 = 1;
   int temp_2 = N;
   int count = 0;
   while (temp_1 <= temp_2){
      int set = (temp_1 + temp_2) >> 1;
      if (set − arr[set] >= K){
         count = set;
         temp_2 = set − 1;
      } else {
         temp_1 = set + 1;
      }
   }
   count = (count ? N − count + 1 : 0);
   return count;
}
int main(){
   int N = 12, K = 5;
   cout<<"Count of numbers < = N whose difference with the count of primes upto them is > = K are: "<<total(N, K);
   return 0;
}

출력

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

Count of numbers < = N whose difference with the count of primes upto them is > = K are: 4