Простыми числами-близнецами называют пары простых чисел, отличающихся на 2, например 11 и 13 или 17 и 19. Найдите все такие пары, в которых большее число не превосходит limit.
Реализуйте twin_primes(limit).
При больших значениях границы найдите все простые числа сразу с помощью решета, а не проверяйте каждое число по отдельности.
Входные данные
limit: наибольшее значение, которое может принимать большее простое число пары.
Выходные данные
Верните список пар [p, p + 2], в которых оба числа простые и p + 2 ≤ limit, отсортированный по возрастанию p. Если таких пар нет, верните пустой список.
Ограничения
0 ≤ limit ≤ 10^6
Примеры
Ввод:
limit = 20
Ожидаемый вывод:
expected = [
[3, 5],
[5, 7],
[11, 13],
[17, 19]
]
Ввод:
long long limit = 20;
Ожидаемый вывод:
std::vector<std::vector<long long>> expected = {
{3, 5},
{5, 7},
{11, 13},
{17, 19}
};
Ввод:
long limit = 20;
Ожидаемый вывод:
long[][] expected = new long[][] {
new long[] {3, 5},
new long[] {5, 7},
new long[] {11, 13},
new long[] {17, 19}
};
Пояснение
Простые числа до 20: 2, 3, 5, 7, 11, 13, 17, 19; пары с разностью 2 дают [[3, 5], [5, 7], [11, 13], [17, 19]].
Ввод:
limit = 6
Ожидаемый вывод:
expected = [
[3, 5]
]
Ввод:
long long limit = 6;
Ожидаемый вывод:
std::vector<std::vector<long long>> expected = {
{3, 5}
};
Ввод:
long limit = 6;
Ожидаемый вывод:
long[][] expected = new long[][] {
new long[] {3, 5}
};
Пояснение
3 и 5 простые, и 5 ≤ 6, но 7 уже больше границы, поэтому остаётся только [[3, 5]].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Решето находит все простые числа до 10^6 гораздо быстрее, чем проверка каждого числа.
Подсказка 2
Затем проверьте каждое p, для которого p + 2 ≤ limit.
Подсказка 3
Первая пара (3, 5), поэтому при любой границе меньше 5 получается пустой список.
Ожидаемая сложность
время O(limit log log limit), доп. память O(limit)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.