1
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Take a look at this. \$\endgroup\$ – Ben Steffan Oct 21 '17 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.