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
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]].
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.