นับจำนวน <=N ที่มีความแตกต่างกับการนับจำนวนเฉพาะที่มากกว่าคือ> =K ใน C++

เมื่อกำหนดจำนวนเต็ม N และ K สองจำนวน เป้าหมายคือการหาจำนวนตัวเลขที่เป็นไปตามเงื่อนไขด้านล่าง -

• เบอร์<=N

• | Number−count |>=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 การนับนี้จะนับเป็น 2 แล้วผลต่าง num+1−count2>=num−count1 ดังนั้นหาก num ถูกต้อง num+1 ก็จะใช้ได้ สำหรับตัวเลขแรกที่พบ ให้พูดว่า 'num' โดยใช้การค้นหาแบบไบนารีที่เป็นไปตามเงื่อนไข จากนั้น 'num'+1 ก็จะเป็นไปตามเงื่อนไขเดียวกัน ด้วยวิธีนี้จะนับตัวเลขทั้งหมดระหว่าง num ถึง N

• รับตัวแปร N และ K เป็นอินพุต

• Array arr[] ใช้เพื่อเก็บจำนวนเฉพาะจนถึง i จะถูกเก็บไว้ที่ดัชนี i.

• ฟังก์ชัน set_prime() อัปเดตอาร์เรย์ arr[] สำหรับจัดเก็บการนับจำนวนเฉพาะ

• Array check[i] จะเก็บ true ถ้า i เป็น prime อย่างอื่นจะเก็บ false

• ตั้งค่า check[0]=check[1] =false เนื่องจากไม่ใช่จำนวนเฉพาะ

• ตรวจสอบการเคลื่อนที่จากดัชนี i=2 ถึง i*i

• ตอนนี้สำรวจ arr[] โดยใช้ for loop และอัปเดต ทั้งหมดนับไม่เกิน arr[i]=arr[i−1] หาก arr[i] เป็นจำนวนเฉพาะ จำนวนนั้นจะเพิ่มขึ้น 1 ตั้ง arr[i]++

• ฟังก์ชัน total(int N, int K) รับค่า N และ K และส่งกลับ Count of numbers <=N ซึ่งมีความแตกต่างกับการนับจำนวนเฉพาะสูงสุดคือ> =K.

• โทร set_prime().

• ใช้ temp_1=1 และ temp_2=N นับเริ่มต้นเป็น 0

• ตอนนี้ใช้การค้นหาแบบไบนารีใน while loop take set =(temp_1 + temp_2)>> 1 ((first+last) /2 )

• หาก set−arr[set] คือ>=K เป็นไปตามเงื่อนไข ให้อัปเดตจำนวนด้วย set และ temp_2=set−1

• มิฉะนั้นให้ตั้งค่า temp_1=temp_1+1

• ที่ชุดสุดท้ายนับเป็นตัวเลขที่ถูกต้องขั้นต่ำ N−count+1 หรือ 0

• ที่ส่วนท้ายของการวนซ้ำทั้งหมดจะนับเป็นผลลัพธ์

ตัวอย่าง

#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