Все задачи
Легко Решено: 0 Процент решений: 0%

Простые числа-близнецы

Найдите все пары простых чисел-близнецов (p, p + 2) до заданной границы.

Чему вы научитесь

  • Отмечать простые числа до границы с помощью решета
  • Искать простые числа, отличающиеся на 2
  • Обрабатывать границы, слишком маленькие для хотя бы одной пары

Условие

Простыми числами-близнецами называют пары простых чисел, отличающихся на 2, например 11 и 13 или 17 и 19. Найдите все такие пары, в которых большее число не превосходит limit.

Реализуйте twin_primes(limit).

При больших значениях границы найдите все простые числа сразу с помощью решета, а не проверяйте каждое число по отдельности.

Входные данные

limit: наибольшее значение, которое может принимать большее простое число пары.

Выходные данные

Верните список пар [p, p + 2], в которых оба числа простые и p + 2 ≤ limit, отсортированный по возрастанию p. Если таких пар нет, верните пустой список.

Ограничения

0 ≤ limit ≤ 10^6

Примеры

Пример 1
Ввод:
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]].

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.