Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> leastPrimceFactor;
- vector<int> primes;
- void sieve(int n) { // O(N)
- leastPrimceFactor.resize(n + 1, 0);
- for(int i = 2; i <= n; ++i) {
- if (leastPrimceFactor[i] == 0) {
- leastPrimceFactor[i] = i;
- primes.push_back(i);
- }
- for (int j = 0; i * primes[j] <= n; ++j) {
- leastPrimceFactor[i * primes[j]] = primes[j];
- if (primes[j] == leastPrimceFactor[i]) {
- break;
- }
- }
- }
- }
- bool isPrime(int n) { // O( sqrt(N) / ln(sqrt(N))) -> tests only primes smaller than sqrt(N)
- if(n == 2) return true;
- if(n < 2 || (n % 2 == 0)) return false;
- if(n < leastPrimceFactor.size()) return leastPrimceFactor[n] == n;
- int index = 0;
- while(primes[index] * primes[index] <= n) {
- if((n % primes[index]) == 0)
- return false;
- index++;
- }
- return true;
- }
- int main() {
- int L = 5;
- int R = 12;
- sieve(sqrt(R) + 1);
- while(L <= R) {
- if(isPrime(L))
- cout << L << ' ';
- ++L;
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement