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
23
24

#include <iostream>
#include <vector>

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