นับจำนวนที่ ≤ N และผลต่างกับจำนวนเฉพาะ ≤ ตัวมัน ≥ K ด้วย C++

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

• Number ≤ N
• | Number - count | ≥ K โดย count คือจำนวนเฉพาะที่ ≤ Number

ตัวอย่าง

Input

N = 5, K = 2

Output

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

Explanation

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

Input

N = 10, K = 6

Output

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

Explanation

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

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ใช้ Binary Search เพื่อลดการคำนวณ ถ้าจำนวนเฉพาะถึง num คือ count1 และถึง num+1 คือ count2 แล้ว num+1-count2 ≥ num-count1 ดังนั้นถ้า num ผ่านเงื่อนไข num+1 ก็จะผ่านเช่นกัน สำหรับตัวเลขแรกที่เจอว่า 'num' ผ่านเงื่อนไข ด้วย binary search แล้ว 'num'+1 ก็จะผ่านเช่นกัน ดังนั้นจำนวนระหว่าง num ถึง N จะถูกนับทั้งหมด

• รับตัวแปร N และ K เป็นอินพุต
• อาร์เรย์ arr[] เก็บจำนวนเฉพาะถึง i ไว้ที่ index i
• ฟังก์ชัน set_prime() อัปเดต arr[] สำหรับนับเฉพาะ
• อาร์เรย์ check[i] เก็บ true ถ้า i เป็นเฉพาะ มิฉะนั้น false
• ตั้ง check[0]=check[1] = false เพราะไม่ใช่เฉพาะ
• วนลูป check จาก i=2 ถึง i*i < size(1000001) ถ้า check[i] เป็น 1 (เป็นเฉพาะ) ตั้ง check[j] = 0 จาก j=i*2 ถึง j < size
• วนลูปอัปเดต arr[] ทุกค่า arr[i] = arr[i-1] ถ้า i เองเป็นเฉพาะ arr[i]++
• ฟังก์ชัน total(int N, int K) คืนค่าจำนวนที่ ≤ N และผลต่างกับจำนวนเฉพาะ ≥ K
• เรียก set_prime()
• กำหนด temp_1=1, temp_2=N, count เริ่มต้น 0
• ใช้ binary search ใน while loop set = (temp_1 + temp_2) >> 1
• ถ้า set - arr[set] >= K เงื่อนไขผ่าน อัปเดต count = set และ temp_2 = set - 1
• มิฉะนั้น temp_1 = set + 1
• ในที่สุด count = ตัวเลขที่ผ่านเงื่อนไขแรก 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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

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