Подразделы

Другие разделы

Дата и время

20/12/2024 15:56:54

Авторизация

Теория чисел

And Now, a Remainder from Our Sponsor Prime Gap Дружественные числа Лоскутное одеяло Простые числа Разложение на простые множители

Prime Gap

Ограничения: время – 500ms/1000ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

The sequence of `n-1` consecutive composite numbers (positive integers that are not prime and not equal to 1) lying between two successive prime numbers `p` and `p\ +\ n` is called a prime gap of length `n`. For example, (24, 25, 26, 27, 28) between 23 and 29 is a prime gap of length 6.

Your mission is to write a program to calculate, for a given positive integer `k`, the length of the prime gap that contains `k`. For convenience, the length is considered 0 in case no prime gap contains `k`.

Input

The input is a sequence of lines each of which contains a single positive integer. Each positive integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709. The end of the input is indicated by a line containing a single zero.

Output

The output should be composed of lines each of which contains a single non-negative integer. It is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or 0 otherwise. No other characters should occur in the output.

Sample Input

Output for the Sample Input