Phương pháp sàng số nguyên tố Sieve of Eratosthenes là một trong những phương pháp hiệu quả nhất trong việc tìm ra các số nguyên tố nhỏ hơn n (n <= 10.000.000).

Ví dụ: Tìm tất cả số nguyên tố nhỏ hơn 50

Bước 1: Xét 2 là số nguyên tố, ta sẽ loại bỏ tất cả bội số của 2 mà lớn hơn hoặc bằng bình phương của 2

Bước 2: Xét 3 là số nguyên tố, ta sẽ loại bỏ tất cả bội số của 3 mà lớn hơn hoặc bằng bình phương của 3

Bước 3: Xét 5 là số nguyên tố, ta sẽ loại bỏ tất cả bội số của 5 mà lớn hơn hoặc bằng bình phương của 5

Ta cứ xét tiếp như vậy, cuối cùng sẽ được:

Tất cả các số còn lại sẽ là số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

#include <bits/stdc++.h>

using namespace std;

vector<int> primes(10000005,0);

void SangSNT(){
    int n = 1000;
    for (int i=2; i*i<=n; i++){
        if (primes[i]==0) {
            for (int j=i*i; j<=n; j+=i){
                primes[j] = 1;
            }
        }
    }

    // In tat ca so nguyen to
    for (int i = 2; i <= n; i++)
        if (primes[i]==0) cout << i << " ";
}

int main()
{
    SangSNT();
    return 0;
}

Hàm upper_bound() trong C++ được sử dụng để trả về phần tử kế tiếp mà lớn hơn giá trị cần tìm. Nếu không tìm thấy sẽ trả về vị trí cuối cùng+1 của mảng. Độ phức tạp hàm upper_bound() là O(logn), n là số lượng phần tử trong mảng.

Ví dụ:

• Mảng [10, 20, 30, 30, 30, 40, 50], Giá trị cần tìm 30. Thì hàm upper_bound sẽ trả về vị trí 5.
• Mảng [10, 20, 30, 30, 30, 40, 50], Giá trị cần tìm 35. Thì hàm upper_bound sẽ trả về vị trí 5.
• Mảng [10, 20, 30, 30, 30, 40, 50], Giá trị cần tìm 55. Thì hàm upper_bound sẽ trả về vị trí 7 (7 = vị trí cuối cùng + 1), có nghĩa là phần tử 55 không tồn tại trong mảng.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // Input vector
    vector<int> v{ 10, 20, 30, 30, 30, 40, 50 };

    auto pos_30 = upper_bound(v.begin(), v.end(), 30);
    auto pos_35 = upper_bound(v.begin(), v.end(), 35);
    auto pos_55 = upper_bound(v.begin(), v.end(), 55);

    cout << "Phan tu 30 nam o vi tri: " << (pos_30 - v.begin()) << endl; // 5
    cout << "Phan tu 35 nam o vi tri: " << (pos_35 - v.begin()) << endl; // 5
    cout << "Phan tu 55 nam o vi tri: " << (pos_55 - v.begin());         // 7

    return 0;
}

Hàm lower_bound() trong C++ được sử dụng để trả về phần tử đầu tiên trong mảng mà có giá trị không bé hơn giá trị cần tìm. Có nghĩa là nó sẽ trả về con số nhỏ nhất mà vừa đủ lớn hơn hoặc bằng con số cần tìm. Nếu trong mảng có nhiều phần tử bằng giá trị cần tìm sẽ trả về phần tử đầu tiên của giá trị đó.

Ví dụ:

• Mảng [10, 20, 30, 40, 50], Giá trị cần tìm 30. Thì hàm lower_bound sẽ trả về vị trí 2.
• Mảng [10, 20, 30, 40, 50], Giá trị cần tìm 35. Thì hàm lower_bound sẽ trả về vị trí 3.
• Mảng [10, 20, 30, 40, 50], Giá trị cần tìm 55. Thì hàm lower_bound sẽ trả về vị trí 5 (5 > vị trí cuối cùng), có nghĩa là phần tử 55 không tồn tại trong mảng.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // Input vector
    vector<int> v{ 10, 20, 30, 30, 30, 40, 50 };

    auto pos_30 = lower_bound(v.begin(), v.end(), 30);
    auto pos_35 = lower_bound(v.begin(), v.end(), 35);
    auto pos_55 = lower_bound(v.begin(), v.end(), 55);

    cout << "Phan tu 30 nam o vi tri: " << (pos_30 - v.begin()) << endl; // 2
    cout << "Phan tu 35 nam o vi tri: " << (pos_35 - v.begin()) << endl; // 5
    cout << "Phan tu 55 nam o vi tri: " << (pos_55 - v.begin());         // 7

    return 0;
}