Grade 10 · Subprograms (functions)Citește în română

Primality function

Original: Funcție de primalitate

OtherC++1754 lines2 examples

The idea

We write the function estePrim(x) once, returning true if x is prime, and call it for every number read. The function looks for a divisor d between 2 and the square root of x (the condition d * d <= x); if it finds one, it exits immediately with return false. 0 and 1 are not prime. n and then n natural numbers are read; the prime ones are printed.

Original description (Romanian)

Scriem o singură dată funcția estePrim(x), care întoarce true dacă x este prim, și o apelăm pentru fiecare număr citit. Funcția caută un divizor d între 2 și radical din x (condiția d * d <= x); dacă găsește unul, iese imediat cu return false. Numerele 0 și 1 nu sunt prime. Se citesc n și apoi n numere naturale; se afișează cele prime.

Complexity
O(n * sqrt(M)), where M is the largest value read
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

6
2 9 13 1 17 20

Expected output

2 13 17
Example 2

Input

4
97 100 0 101

Expected output

97 101

The code

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

functie-de-primalitate.cpp
/*
 * Titlu: Funcție de primalitate
 * Clasa: 10
 * Capitol: Subprograme (funcții)
 * Descriere: Scriem o singură dată funcția estePrim(x), care întoarce true dacă
 *            x este prim, și o apelăm pentru fiecare număr citit. Funcția caută
 *            un divizor d între 2 și radical din x (condiția d * d <= x); dacă
 *            găsește unul, iese imediat cu return false. Numerele 0 și 1 nu sunt prime.
 *            Se citesc n și apoi n numere naturale; se afișează cele prime.
 * Complexitate: O(n * sqrt(M)), unde M este cea mai mare valoare citită
 *
 * Exemplu
 * Intrare:
 * 6
 * 2 9 13 1 17 20
 * Ieșire: 2 13 17
 *
 * Exemplu
 * Intrare:
 * 4
 * 97 100 0 101
 * Ieșire: 97 101
 */
#include <iostream>
using namespace std;

// Întoarce true dacă x este număr prim.
bool estePrim(int x)
{
    if (x < 2)
        return false;
    for (int d = 2; d * d <= x; d++)
    {
        if (x % d == 0)
            return false;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (estePrim(x))
            cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

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