math/primeSieve.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ll;

vector<int> primeSieve(ll n) {
	vector<int> primes;
	vector<int> isPrime(n,true);
	for(ll i = 2; i < n; i+=2) {
		if(isPrime[i]) {
			primes.push_back(i);
			if(i*i <= n) {
				for(ll j = i; i*j < n; j+=2) isPrime[i*j] = false;
			}
		}
		if(i == 2)
			i--;
	}
	return primes;
}