Go: package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	io := NewIo()
	defer io.Flush()
	isPrime := Sieve(1299709)
	for {
		k := io.NextInt()
		if k == 0 {
			break
		}
		ans := 0
		if !isPrime[k] {
			p, n := k-1, k+1
			for !isPrime[p] || !isPrime[n] {
				if !isPrime[p] {
					p--
				}
				if !isPrime[n] {
					n++
				}
			}
			ans = n - p
		}
		io.Println(ans)
	}
}

func Sieve(x int) []bool {
	flags := make([]bool, x+1)
	for i := 2; i <= x; i++ {
		flags[i] = true
	}
	for i := 2; i <= int(math.Sqrt(float64(x))); i++ {
		if !flags[i] {
			continue
		}
		for j := i * i; j <= x; j += i {
			flags[j] = false
		}
	}
	return flags
}

// I/O template
type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func NewIo() *Io {
	return &Io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *Io) NextLine() string {
	var buff []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buff = append(buff, line...)
		if !isPrefix {
			break
		}
	}
	return string(buff)
}

func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	s := io.tokens[io.nextToken]
	io.nextToken++
	return s
}

func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *Io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func (io *Io) PrintIntSlice(a []int) {
	b := make([]interface{}, 0, len(a))
	for _, x := range a {
		b = append(b, x)
	}
	io.Println(b...)
}

func (io *Io) PrintStringSlice(a []string) {
	b := make([]interface{}, 0, len(a))
	for _, x := range a {
		b = append(b, x)
	}
	io.Println(b...)
}

func Log(name string, value interface{}) {
	fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}

func ExampleIo() {
	io := NewIo()
	defer io.Flush()
	a := make([]int, 0, 3)
	a[0], a[1], a[2] = io.NextInt(), io.NextInt(), io.NextInt()
	io.Println(a)
	io.PrintIntSlice(a)
	Log("io", a)
}

Python: # coding: utf-8
# Your code here!
# input
def horizontal_input(T=str,debug=False):
    data = list(map(T,input().split()))
    if debug:
        print(*data)
    return data

def vertical_input(n,T=str,sep=False,septype=list,debug=False):
    data=[]
    if sep:
        for i in range(n):
            data.append(septype(map(T,input().split())))
    else:
        for i in range(n):
            data.append(T(input()))
    if debug:
        print(*data,sep='\n')
    return data

# Eratosthenes
def eratosthenes(n):
    prime_table = [False,False,True]+[False if i%2!=0 else True for i in range(n-2)]
    i=3
    while i*i<=n:
        if prime_table[i]:
            j=i*i
            while j<=n:
                prime_table[j]=False
                j+=i
        i+=2
    return prime_table

prime_table = eratosthenes(2000000)
primes=[]
for i in range(len(prime_table)):
    if prime_table[i]:
        primes.append(i)

while 1:
    n=int(input())
    if n==0:
        break
    i=0
    while primes[i]<=n:
        i+=1
    i=primes[i-1]
    if i==n:
        print(0)
    else:
        count=1
        j=i+1
        while 1:
            if prime_table[j]:
                break
            j+=1
            count+=1
        print(count)

Python: def sieve():
    L = 1299710
    primes = []
    isPrime = [ True for _ in range(L) ]
    for i in range(2, L):
        if isPrime[i]:
            primes.append(i)
            for j in range(i * i, L, i):
                isPrime[j] = False
    return primes

def getPrimeGap(num, primes):
    if num in primes:
        return 0

    for i in range(100000 - 1):
        if primes[i] < num and primes[i + 1] > num:
            return primes[i + 1] - primes[i]

if __name__ == '__main__':
    primes = sieve()
    while True:
        num = int(input())
        if num == 0:
            break

        print(getPrimeGap(num, primes))

Python: def make_prime_table(n):
    """n以下の非負整数が素数であるかを判定したリストを出力する
    計算量: O(NloglogN)
    入出力例: 6 -> [False, False, True, True, False, True, False]
    """
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    return is_prime


is_prime = make_prime_table(2 * 10 ** 6)
while True:
    n = int(input())
    if n == 0:
        break
    l = n
    r = n
    while not is_prime[l]:
        l -= 1
    while not is_prime[r]:
        r += 1
    print(r - l)

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-

import math

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

primeTable = sieve_of_erastosthenes(13*10**5)

while True:
    k = int(input())
    if k == 0:
        break
    if primeTable[k]:
        print(0)
    else:
        i = 0
        while i < k or primeTable[i] == False:
            if primeTable[i]:
                prevPrime = i
            i+= 1
        print(i-prevPrime)

Python: #!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import bisect


MAX_PRIME = 1299709


def sieve_of_eratosthenes(end, typecode="L"):
    assert end > 1
    is_prime = array.array("B", (True for i in range(end)))
    is_prime[0] = False
    is_prime[1] = False
    primes = array.array(typecode)
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


def main():
    primes = sieve_of_eratosthenes(MAX_PRIME + 1)

    def length_of_gap_containing(n):
        index = bisect.bisect_left(primes, n)
        next_prime = primes[index]
        if next_prime == n:
            return 0
        else:
            prev_prime = primes[index - 1]
            return next_prime - prev_prime
    while True:
        n = int(input())
        if n == 0:
            break
        else:
            print(length_of_gap_containing(n))


if __name__ == '__main__':
    main()

Python: prime = [True for i in range(1300001)]
prime[0] = prime[1] = False
for i in range(2, 1200):
    if prime[i]:
        for j in range(2, 1300000 // i + 1):
            prime[i * j] = False

while True:
    n = int(input())
    if n == 0:
        break

    nl = nu = n
    while not prime[nl]:
        nl -= 1
    while not prime[nu]:
        nu += 1
    print(nu - nl)

Python: import math
def sieve (n):
	prime = [0,0]
	prime += [1 for i in range(n-1)]
	ub = math.sqrt(n) + 1
	d = 2
	while d <= ub:
		if prime[d] == 0:
			d += 1
			continue
		prod = 2
		while d * prod <= n:
			prime[d*prod] = 0
			prod += 1
		d += 1
	return prime
prime = sieve(1299709)
while 1:
	k = int(raw_input())
	if k == 0:
		break
	l = r = k
	while prime[l] == 0:
		l -= 1
	while prime[r] == 0:
		r += 1
	print (r-1) - (l+1) + 2