# Sàng Linear

---

**Tác giả : [Dương Nguyên Khánh](https://github.com/kduongnguyen07)</a>**
---
###### tags:`Number Theory`,`Sieve`,`Prime Numbers`
# **Mở đầu**
Số nguyên tố từ lâu nay luôn là một loại số có xuất hiện nhiều trong các cuộc thi và có áp dụng lớn đến cuộc sống
## Một số kỹ thuật kiểm tra số nguyên tố

- Kiểm tra Rabin-Miller
- Sử dụng các loại sàng
- Chạy trâu

# Cơ chế hoạt động
## ***Chạy trâu***
Với mọi số nguyên x trong đoạn [0,n]. Ta đếm số ước d của x trong đoạn [0,x]. Nếu x có đúng 2 ước thì x là số nguyên tố

#include <bits/stdc++.h>
using namespace std;
const int LIM = 1e6;
bool checkPrime(int n)
{
    int cnt = 0;
    for (int d = 1; d <= n; ++d)
        if (n % d == 0)
            ++cnt;

    return cnt == 2;
}
int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{
    cntPrime = 0;
    for (int x = 0; x <= n; ++x)
    {
        if (checkPrime(x))
        {
            ++cntPrime;
            isPrime[x] = true;
        }
    }
}

## ***Sàng Eratosthenes***
Nhận thấy rằng các số có nhiều ước thì sẽ bị đánh dấu nhiều lần. Vì khi x là hợp số, thì với mọi ước v của x, thì bội kx của x cũng là bội của v. Nên để hạn chế điều đó, ta chỉ đánh dấu các bội của x khi x là số nguyên tố.

#include <bits/stdc++.h>
using namespace std;
const int LIM = 1e6;
int cntPrime;
bool isPrime[LIM + 1];
void sieve(int n)
{
    memset(isPrime, true, sizeof(isPrime[0]) * (n + 1));
    isPrime[0] = isPrime[1] = false;

    for (int p = 2; p * p <= n; ++p) if (isPrime[p])
        for (int x = p + p; x <= n; x += p) 
            isPrime[x] = false;

    cntPrime = 0;
    for (int p = 0; p <= n; ++p) cntPrime += isPrime[p];
}

## ***Sàng Eratosthenes cải tiến bằng Linear Search***
Nhưng, với cách trên thì mình vẫn phải đánh dấu nhiều lần các số có nhiều ước nguyên tố.
Ta gọi lpf[x] là ước nguyên tố nhỏ nhất của x
(viết tắt của lowest_prime_factor)
Khi này mọi số x>1
đều có thể được biểu diễn bằng x=k×lpf[x]. Mà từ định nghĩa ta có lpf[x]≤lpf[k]
**Cài đặt**

#include <bits/stdc++.h>
using namespace std;
const int LIM = 1e6; //giới hạn đến 10^6
vector<int> prime;
vector<int> lpf;
void sieve(int n)
{
    prime.assign(1, 2);
    lpf.assign(n + 1, 2);
    for (int x = 3; x <= n; x += 2)
    {
        if (lpf[x] == 2) prime.push_back(lpf[x] = x);
        for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= n; ++i)
            lpf[prime[i] * x] = prime[i];
    }
}
/*
Cách này khi gọi cout<<prime.size() 
thì sẽ in ra được số phần tử là số nguyên tố đến N
*/

**Nếu muốn in ra tất cả các phần tử là số nguyên tố nhỏ hơn hoặc bằng N**

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N = 10000000;
vector<int> lp(N+1);
vector<int> pr;
int main()
{   cin>>N;
    for (int i=2; i <= N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back(i);
    }
    for (int j = 0; i * pr[j] <= N; ++j) {
        lp[i * pr[j]] = pr[j];
        if (pr[j] == lp[i]) {
            break;
        }
    }
    }
    for (auto x:pr)
    {
        cout<<x<<" ";
    }
}

Độ phức tạp thời gian : O(N)