Формула для простых чисел

Сегодня у нас два простых вопроса про простые числа.

Для начала: сколько всего простых чисел? На этот вопрос ответил Евклид ещё в 3 веке до нашей эры: их бесконечное количество. Это легко доказать, так сделаем это!

Предположим обратное — допустим, простых чисел конечное количество. Тогда есть «самое большое простое число», пусть оно равно p. Перемножим все простые числа до p включительно, а затем прибавим к произведению 1. Результат не делится нацело ни на одно из предыдущих простых чисел, и уж тем более ни на одно из составных. Получается, что результат делится только сам на себя и на 1, а значит — это простое число. Этот способ всегда позволяет сконструировать новое простое число, которое больше «самого последнего». Значит, простых чисел бесконечное количество. Доказали.👌

Теперь второй вопрос: как найти простое число, зная только его номер?
Есть решето Эратосфена — о нём мы писали ранее. Этот алгоритм позволяет последовательно находить все простые числа. Но есть проблема: с увеличением чисел время на его реализацию растёт с огромной скоростью. Поэтому этот алгоритм неудобно использовать, чтобы найти очень большие простые числа.

Удобным вариантом была бы формула, которая по номеру простого числа помогала бы вычислить само число. К сожалению, попытки найти такую формулу не привели к успеху.

Лучшее, что получалось, — формулы, которые выдают простые числа часто, но не всегда. Одну из таких формул предложил известный математик Леонард Эйлер. Выглядит она так:
n² - n + 41. Числа, рассчитанные по ней, являются простыми для n = 0, 1, …, 40. Но при n = 41 значение обращается в 41² — а это уже составное число. При n = 42 тоже неудача.

Однако при n = 43 и дальше формула снова работает — часто, но не всегда. Определите, при каком n она ломается в следующий раз? Ответы присылайте под скрытым текстом.