---
# System prepended metadata

title: Prime

---

# Prime

## 埃式篩

```cpp=
void Sieve(int N){
    vector<bool> isprime(N,true);
    for(int i=2;i<N;i++){
        if(isprime[i]){
            for(int j=i*i;j<N;j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2;i<N;i++){
        if(isprime[i]) cout << i << ' ';
    }
}
```

## 線性篩

```cpp=
void Linear_Sieve(int N){
    vector<int> prime;
    vector<bool> isprime(N,true);
    for(int i=2;i<N;i++){
        if(isprime[i]) prime.pb(i);
        for(auto j:prime){
            if(i*j>=N) break;
            isprime[i*j]=false;
            if(i%j==0) break;
        }
    }
    for(auto i:prime) cout << i << ' ';
}
```
