Grade 9 · Divisibility and prime numbersCitește în română

The first n prime numbers

Original: Primele n numere prime

OtherC++1740 lines1 example

The idea

We take the candidates 2, 3, 4, ... one by one and test them with the primality test up to √x. We stop after printing n prime numbers.

Original description (Romanian)

Luăm pe rând candidații 2, 3, 4, ... și îi testăm cu testul de primalitate până la √x. Ne oprim după ce am afișat n numere prime.

Complexity
about O(n · √P), where P is the n-th prime number
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

10

Expected output

2 3 5 7 11 13 17 19 23 29

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

primele-n-numere-prime.cpp
/*
 * Titlu: Primele n numere prime
 * Clasa: 9
 * Capitol: Divizibilitate și numere prime
 * Descriere: Luăm pe rând candidații 2, 3, 4, ... și îi testăm cu testul de
 *            primalitate până la √x. Ne oprim după ce am afișat n numere prime.
 * Complexitate: aproximativ O(n · √P), unde P este al n-lea număr prim
 *
 * Exemplu
 * Intrare: 10
 * Ieșire: 2 3 5 7 11 13 17 19 23 29
 */
#include <iostream>
using namespace std;

int main()
{
    int n, gasite = 0;
    cin >> n;
    for (long long x = 2; gasite < n; x++)
    {
        bool prim = true;
        for (long long d = 2; d * d <= x; d++)
        {
            if (x % d == 0)
            {
                prim = false;
                break;
            }
        }
        if (prim)
        {
            cout << x << ' ';
            gasite++;
        }
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.