# Printing all prime numbers up to N

I have an algorithm to print all prime numbers in interval [2..N]:

void print_primes(int n) {
std::vector<int> nums;

for (int i = 0; i < n - 1; ++i) {
nums.push_back(i + 2);
}

for (int i = 2; i <= n;) {
std::cout << i << ' ';

bool is_first = true;
int cur = i;

for (int j = i - 1; j < static_cast<int>(nums.size()); ++j) {

if (nums[j] > 0) {

if (nums[j] % cur == 0) {
nums[j] *= -1;
} else if (is_first) {
i = nums[j];
is_first = false;
}
}
}

if (is_first) {
break;
}
}
}


The problem is that I need to execute it for O(N) and I haven't ideas already... How to optimize it for O(N)?
Now, it works just marking next non-prime numbers to exclude it.

• Take a look at this. – Ben Steffan Oct 21 '17 at 9:30