โปรแกรม C++ พิมพ์จำนวนเฉพาะในช่วงที่กำหนดด้วย C++ STL

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมพิมพ์จำนวนเฉพาะสำหรับช่วงตัวเลขที่กำหนดโดยใช้ C++ Standard Template Library

ในนี้ เราจะได้รับตัวเลขสองตัว คือ a และ b งานคือพิมพ์จำนวนเฉพาะทั้งหมดในช่วงนี้ สำหรับนี้ เราจะใช้วิธี Sieve of Eratosthenes โดยรันเป็น subroutine พร้อมกันเราจะเก็บจำนวนเฉพาะทั้งหมดใน vector และสุดท้ายพิมพ์ทั้งหมด

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

typedef unsigned long long int unll; 

vector<unll> eratosthemes(unll n){ 
    vector<bool> prime_num(n + 1, true); 
    prime_num[0] = false; 
    prime_num[1] = false; 
    int m = sqrt(n); 
    for (unll p = 2; p <= m; p++){ 
        if (prime_num[p]){ 
            for (unll i = p * 2; i <= n; i += p) 
                prime_num[i] = false; 
        } 
    } 
    vector<unll> elements; 
    for (int i = 0; i < n; i++) 
        if (prime_num[i]) 
            elements.push_back(i); 
    return elements; 
} 

bool check_zero(unll i){ 
    return i == 0; 
} 

vector<unll> sieve_range(unll start, unll end){ 
    vector<unll> s1 = eratosthemes(start); 
    vector<unll> s2 = eratosthemes(end); 
    vector<unll> elements(end - start); 
    set_difference(s2.begin(), s2.end(), s1.begin(), s2.end(), elements.begin()); 
    vector<unll>::iterator itr = remove_if(elements.begin(), elements.end(), check_zero); 
    elements.resize(itr - elements.begin()); 
    return elements; 
} 

int main(void){ 
    unll start = 10; 
    unll end = 90; 
    vector<unll> elements = sieve_range(start, end); 
    for (auto i : elements) 
        cout << i << ' '; 
    return 0; 
}

ผลลัพธ์

11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89