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

Pairs of twin primes

Original: Perechi de numere prime gemene

OtherC++1745 lines1 example

The idea

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.

Original description (Romanian)

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.

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

Examples

Example 1

Input

20

Expected output

3 5
5 7
11 13
17 19

The code

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

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;
}

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