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)
}

C++: //include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <math.h>

using namespace std;

//conversion
//------------------------------------------
inline long toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline long toLong(string s) {long v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

//constant
//--------------------------------------------

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const long double EPS = 1e-6;
const long INF = 1e10;


int main(){
	int n;
	vector<long>prime;
	for(long i=2;i<=1299709;i++){
		bool flag=true;
		for(long j=2;j*j<=i;j++)if(i%j==0){
			flag=false;break;
		}
		if(flag)prime.PB(i);
	}
	while(cin>>n){
		if(n==0)break;
		vector<long>::iterator itr=lower_bound(ALL(prime),n);
		if(*itr==n){
			cout<<0<<endl;
		}else{
			long ma=*itr;
			itr--;
			cout<<ma-*itr<<endl;
		}
	}
	return 0;
}

C++: #include <iostream>
bool isPrime(int x) {for(int i=2;i*i<=x;i++)if(x%i==0)return false;return true;}
int main() {
  int n;
  while(std::cin>>n,n) {
    int ans=0;
    for(int s=-1;s<2;s+=2)for(int i=0;!isPrime(n+i*s);i++,ans++);
    std::cout<<ans<<'\n';
  }
  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define mp(a,b) make_pair((a),(b))
#define eq ==

typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> pii;

// →↑←↓
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};


const double EPS = 1e-9;

const int M = 1299800;
bool isPrime[M];

vector<int> primes;

void sieve(){
    for(int i=2;i<M;i++) isPrime[i] = true;
    for(int i=2;i*i < M;i++){
        if(!isPrime[i]) continue;
        for(int j=i*i;j<M;j+=i){
            isPrime[j] = false;
        }
    }
    for(int i=2;i<M;i++) {
        if(isPrime[i]) primes.push_back(i);
    }
}

int main(){
    sieve();
    while(true){
        int n;
        cin >> n;
        if(isPrime[n]){
            cout << 0 << endl;
        }else{
            cout << (*upper_bound(all(primes),n)) -  *(upper_bound(all(primes),n)-1) << endl;
        }
    }
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#define rep(i, n) for(int i = 0; i < n; i ++)
#define COUNT(i, n) for(int i = 1; i <= n; i ++)
#define ITER(c) __typeof((c).begin())
#define each(c, it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define ALL(c) c.begin(), c.end()
#define mp make_pair
#define pb push_back
#define MEMSET(v, h) memset((v), h, sizeof(v))
 
using namespace std; 

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

const int INF = 1 << 24;

int main(void){
	const int N = (int)1e6;
	bool isP[N];
	rep(i, N) isP[i] = true;
	for(int i = 2; i * i < N; i ++) if(isP[i]) for(int j = i; i * j < N; j ++) isP[i * j] = false;

    for(int n, r, res; cin >> n, n; cout << res << endl){
        r = n;
        if(isP[n]) res = 0;
        else{
            while(!isP[--r]);
            while(!isP[++n]);
        }
        res = n - r;
    }

    return 0;
}

C++: #include <bits/stdc++.h>
#define Msize 1300000
using namespace std;
 
bool prime[Msize] = {0};
 
void setp(){
    prime[0] = prime[1] = 1;
    for(int i = 2;i < Msize;++i)
        if(!prime[i])
            for(int j = 2;j * i < Msize;++j)
                prime[i * j] = 1;
}
 
int x;
 
int solve();
 
int main(){
    setp();
    while(1){
        cin >> x;
        if(x == 0)break;
        cout << solve() << endl;
    }
    return 0;
}
 
int solve(){
    if(!prime[x])return 0;
    int ans = 0,now = x;
    while(prime[now])++ans,++now;
    now = x;
    while(prime[now])++ans,--now;
    return ans;
}