Primes up to N

Lab C++ Intermediate 20 points

Read n and print all primes ≤ n on one line.

Input

One integer ≥ 2.

Output

One line.

Example

Input

Output

2 3 5 7 11 13 17 19 23 29

Sample input available Sample output available

Editor

C++

Hints

Test divisors up to the square root and break on the first one.

Solution explanation

The inner break leaves only the inner loop.

Show solution

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool first = true;
    for (int x = 2; x <= n; x++) {
        bool prime = true;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) {
                prime = false;
                break;
            }
        }
        if (prime) {
            cout << (first ? "" : " ") << x;
            first = false;
        }
    }
    cout << "\n";
    return 0;
}

Output

Answer