/*
 * Copyright (c) 2007 Kamo Hiroyasu
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * ACM ICPC 2007 Asia Regional Contest, Tokyo
 *  Problem B  Prime Gap
 *   Author: Kamo Hiroyasu <wd@ics.nara-wu.ac.jp>
 */

#include <stdio.h>
#include <stdlib.h>

#define INPUT_LIMIT	1299709
#define SQRT_INPUT_LIMIT	1140

int
isprime(unsigned n)
{
	static char	*sieve;
	if (!sieve) {
		const size_t	sieve_size = INPUT_LIMIT + 1;
		unsigned	i, j;

		sieve = calloc((sieve_size + 7) / 8, sizeof(char));
		if (!sieve) {
			perror(NULL);
			exit(2);
		}
		sieve[0] |= 3;
		for (i = 2; i <= SQRT_INPUT_LIMIT; ) {
			for (j = i * i; j < sieve_size; j += i) {
				sieve[j / 8] |= 1 << j % 8;
			}
			do {
				++ i;
			} while ((sieve[i / 8] & 1 << i % 8) != 0);
		}
	}
	return (sieve[n / 8] & 1 << n % 8) == 0;
}

unsigned
prime_gap_length(unsigned x)
{
	unsigned	m, n;

	if (x < 2 || isprime(x))
		return 0;
	m = x + 1;
	while (!isprime(m)) {
		m ++;
	}
	n = x - 1;
	while (!isprime(n)) {
		n --;
	}
	return m - n;
}

int
main(int argc, char *argv[])
{
	const char	*path = "B.in";
	char		*cmd;
	FILE		*fp;
	unsigned	x;

	cmd = argv[0];
	argc --;
	argv ++;
	switch (argc) {
	case 1:
		path = *argv;
	case 0:
		break;
	default:
		fprintf(stderr, "%s: too many arguments\n", cmd);
		exit(1);
	}
	if ((fp = fopen(path, "r")) == NULL) {
		perror(path);
		exit(2);
	}
	while (fscanf(fp, "%u", &x) == 1 && x != 0) {
#ifndef NDEBUG
		if (x <= 1 || x > INPUT_LIMIT) {
			printf("*\n");
			continue;
		}
#endif
		printf("%u\n", prime_gap_length(x));
	}
	return 0;
}