Clasa a IX-a · Divizibilitate și numere primeRead in English

Perechi de numere prime gemene în C++

În engleză: Pairs of twin primes

Altă complexitateC++1745 de linii1 exemplu

Ideea

Două numere prime sunt gemene dacă diferența lor este 2 (de exemplu 11 și 13). Afișăm toate perechile (p, p + 2) cu p + 2 <= n, testând primalitatea ambelor numere până la √x.

Descrierea în engleză

Two prime numbers are twins if their difference is 2 (for example 11 and 13). We print all pairs (p, p + 2) with p + 2 <= n, testing both numbers for primality up to √x.

Complexitate
O(n · √n)
Clasa
Clasa a IX-a (Grade 9)

Exemple

Exemplul 1

Intrare

20

Ieșire așteptată

3 5
5 7
11 13
17 19

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

numere-prime-gemene.cpp
/*
 * Titlu: Perechi de numere prime gemene
 * Clasa: 9
 * Capitol: Divizibilitate și numere prime
 * Descriere: Două numere prime sunt gemene dacă diferența lor este 2
 *            (de exemplu 11 și 13). Afișăm toate perechile (p, p + 2) cu
 *            p + 2 <= n, testând primalitatea ambelor numere până la √x.
 * Complexitate: O(n · √n)
 *
 * Exemplu
 * Intrare: 20
 * Ieșire:
 * 3 5
 * 5 7
 * 11 13
 * 17 19
 */
#include <iostream>
using namespace std;

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

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.