Tutte le sfide
Facile 0 risolte 0% di accettazione

Numeri primi gemelli

Elenca tutte le coppie di primi gemelli (p, p + 2) fino a un certo limite.

Cosa imparerai

  • Segnare con un crivello i primi fino a un limite
  • Cercare i primi che distano due
  • Gestire limiti troppo piccoli per contenere una coppia

Problema

I primi gemelli sono due numeri primi che differiscono di 2, come 11 e 13 oppure 17 e 19. Trova tutte le coppie di questo tipo in cui il numero maggiore non supera limit.

Implementa twin_primes(limit).

Con limiti grandi conviene trovare tutti i primi in una volta sola con un crivello, invece di verificare ogni numero separatamente.

Input

limit: il valore massimo che può avere il primo maggiore di una coppia.

Output

Restituisci una lista di coppie [p, p + 2] in cui entrambi i numeri sono primi e p + 2 ≤ limit, ordinate per p in ordine crescente. Se non ci sono coppie, restituisci una lista vuota.

Vincoli

0 ≤ limit ≤ 10^6

Esempi

Esempio 1
Input:
limit = 20

Output atteso:
expected = [
    [3, 5],
    [5, 7],
    [11, 13],
    [17, 19]
]
Input:
long long limit = 20;

Output atteso:
std::vector<std::vector<long long>> expected = {
    {3, 5},
    {5, 7},
    {11, 13},
    {17, 19}
};
Input:
long limit = 20;

Output atteso:
long[][] expected = new long[][] {
    new long[] {3, 5},
    new long[] {5, 7},
    new long[] {11, 13},
    new long[] {17, 19}
};

Spiegazione

I primi fino a 20 sono 2, 3, 5, 7, 11, 13, 17, 19; quelli che distano 2 danno [[3, 5], [5, 7], [11, 13], [17, 19]].

Esempio 2
Input:
limit = 6

Output atteso:
expected = [
    [3, 5]
]
Input:
long long limit = 6;

Output atteso:
std::vector<std::vector<long long>> expected = {
    {3, 5}
};
Input:
long limit = 6;

Output atteso:
long[][] expected = new long[][] {
    new long[] {3, 5}
};

Spiegazione

3 e 5 sono entrambi primi e 5 ≤ 6, ma 7 supera il limite, quindi resta solo [[3, 5]].

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Un crivello trova tutti i primi fino a 10^6 molto più in fretta che verificare ogni numero.

Suggerimento 2

Poi controlla ogni p con p + 2 ≤ limit.

Suggerimento 3

La prima coppia è (3, 5), quindi qualsiasi limite minore di 5 dà una lista vuota.

Complessità attesa

tempo O(limit log log limit), spazio aggiuntivo O(limit)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.