In số nguyên tố trong khoảng cho trước dùng C++ STL

Chương trình in các số nguyên tố trong một khoảng cho trước.

Thuật toán

Bắt đầu
  Khai báo kiểu dữ liệu người dùng stl.
  Khai báo vector number kiểu stl.
  Khai báo biến a kiểu stl.
  Khai báo vector Prime_Number kiểu Boolean.
    Prime_Number[0] = false.
    Prime_Number[1] = false.
  Khai báo b kiểu nguyên.
    Khởi tạo b = sqrt(a).
  for (stl pr = 2; pr <= b; pr++)
    if (Prime_Number[pr]) thì
      for (stl i = pr*2; i <= a; i += pr)
        Prime_Number[i] = false.
  Khai báo result kiểu vector.
  for (int i = 0; i < a; i++)
    if (Prime_Number[i]) thì
      result.push_back(i).
    trả về result.
Kết thúc
Bắt đầu
  Khai báo hàm remove_zero() kiểu Boolean.
  Khai báo i kiểu stl.
  Trả về i == 0.
Kết thúc
Bắt đầu
  Khai báo vector Number_Range kiểu stl.
  Khai báo First_Num, Last_Num kiểu stl.
  Truyền chúng làm tham số.
  Khai báo hai vector s1 và s2 kiểu stl.
    Khởi tạo s1 = number(First_Num) để tìm số nguyên tố từ 0 đến First_Num.
    Khởi tạo s2 = number(Last_Num) để tìm số nguyên tố từ 0 đến Last_Num.
  Khai báo vector result(Last_Num - First_Num) kiểu stl.
  Gọi set_difference(s2.begin(), s2.end(), s1.begin(), s2.end(), result.begin()) để tìm hiệu hai vector.
  Khai báo iterator itr kiểu vector.
    Khởi tạo itr = remove_if(result.begin(), result.end(), remove_zero) để loại bỏ số 0 thừa.
  Gọi resize(itr - result.begin()) để thay đổi kích thước result.
  Trả về result.
  Khai báo First_Num, Last_Num kiểu stl.
    Khởi tạo First_Num = 20, Last_Num = 50.
  Khai báo vector result kiểu stl.
    Khởi tạo result = Number_Range(First_Num, Last_Num).
  In "The Prime Numbers from 20 to 50 are: "
  for (auto i : result)
    In giá trị i.
Kết thúc.

Ví dụ

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

typedef unsigned long long int stl;

vector<stl> number(stl a) {
  vector<bool> Prime_Number(a+1, true);
  Prime_Number[0] = false;
  Prime_Number[1] = false;
  int b = sqrt(a);
  for (stl pr = 2; pr <= b; pr++) {
    if (Prime_Number[pr]) {
      for (stl i = pr*2; i <= a; i += pr)
        Prime_Number[i] = false;
    }
  }
  vector<stl> result;
  for (int i = 0; i < a; i++)
    if (Prime_Number[i])
      result.push_back(i);
  return result;
}

bool remove_zero(stl i) {
  // Dùng để loại bỏ số 0 khỏi vector
  return i == 0;
}

vector<stl> Number_Range(stl First_Num, stl Last_Num) {
  vector<stl> s1 = number(First_Num); // tìm số nguyên tố từ 0 đến First_Num
  vector<stl> s2 = number(Last_Num); // tìm số nguyên tố từ 0 đến Last_Num
  vector<stl> result(Last_Num - First_Num);
  set_difference(s2.begin(), s2.end(), s1.begin(), s2.end(), result.begin()); // tìm hiệu hai vector
  vector<stl>::iterator itr = remove_if(result.begin(), result.end(), remove_zero); // loại bỏ số 0 thừa
  result.resize(itr - result.begin());
  return result;
}

int main(void) {
  stl First_Num = 20, Last_Num = 50;
  vector<stl> result = Number_Range(First_Num, Last_Num);
  cout << "The Prime Numbers from " << First_Num << " to " << Last_Num << " are: ";
  for (auto i : result)
    cout << i << ' ';
  return 0;
}

Kết quả

The Prime Numbers from 20 to 50 are: 23 29 31 37 41 43 47