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<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<cassert>
#include<sstream>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

template<int m>
class Prime{
  std::vector<bool> p;
public:
  std::vector<int> ps;
  Prime(){
    p = std::vector<bool>(m,true);
    assert(m>1);
    p[0]=p[1]=false;
    for(int i=4;i<m;i+=2)
      p[i]=false;
    ps.push_back(2);
    for(int i=3;i<m;i+=2){
      if(p[i]){
        ps.push_back(i);
        for(int j=i+i;j<m;j+=i)
          p[j]=false;
      }
    }
  }

  bool isPrime(int n){
    assert(m>n);
    return p[n];
  }

  int operator [] (int n){
    if(n<ps.size()) return ps[n];
    else return 0;
  }

  int size(){
    return ps.size();
  }
};

int main(){
  Prime<1299710> p;
  vector<int> &v = p.ps;

  int n;
  while(scanf("%d",&n), n){
    vector<int>::iterator it = lower_bound(ALL(v), n);
    if(n == 2 || *it == n){
      puts("0");
    }else{
      printf("%d\n",*it - *(it-1));
    }
  }
  return 0;
}

C++: // Prime Gap
// English only

#include <iostream>

using namespace std;

const int Size = 1299710;

int main() {
  int k;
  bool prime[Size];
  fill(prime, prime+Size, true);
  prime[0]=prime[1]=false;
  for(int i=2; i<Size; i++) {
    if(prime[i]) { // iが素数であれば
      for(int j=2; i*j<Size; j++) {
	prime[i*j] = false;
      }
    }
  }

  while(1) {
    cin>>k;
    if(k==0) {
      break;
    }

    int l=k, r=k;
    while(!prime[l]) {
      l--;
    }
    while(!prime[r]) {
      r++;
    }
    cout<<r-l<<endl;
  }
}

C++: #include <iostream>
#include <algorithm>
using namespace std;

const int M = 1300000;

bool p[M];

void prime() {
  fill(p, p+M, true);
  p[0] = p[1] = false;
  for(int i = 2; i*i < M; i++) {
    if(p[i]) {
      for(int j = 2; i*j < M; j++) {
        p[i*j] = false;
      }
    }
  }
}

int main() {
  prime();
  int n;
  while(cin >> n, n) {
    int ans = 0;
    for(int i = n; !p[i]; i--) ans++;
    for(int i = n; !p[i]; i++) ans++;
    cout << ans << endl;
  }
}

C++: #include<cstdio>
#include<vector>
#include<algorithm>

#define	pb			push_back
#define	rep(i,n)	for(int i=0;i<n;i++)

using namespace std;

typedef	vector<int>	vi;

int main(){
	const int Ne=1299910;
	static bool er[Ne]; er[0]=er[1]=true;
	for(int i=2;i*i<Ne;i++) if(!er[i]) for(int j=i*i;j<Ne;j+=i) er[j]=true;
	vi p; rep(i,Ne) if(!er[i]) p.pb(i);

	for(int n;scanf("%d",&n),n;){
		vi::iterator itl=lower_bound(p.begin(),p.end(),n),itu=upper_bound(p.begin(),p.end(),n);
		printf("%d\n",*itl-*(itu-1));
	}

	return 0;
}

C++: #include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

bool prime[1000000];
int gap[1000000];

int main(){
	rep(i,1000000)prime[i]=true;
	prime[0]=prime[1]=false;
	loop(i,2,1000)for(int j=i*2;j<1000000;j+=i)prime[j]=false;
	rep(i,1000000)gap[i]=-1;
	int pre=2;
	loop(i,3,1000000){
		if(prime[i]){
			gap[i]=i-pre;
			pre=i;
		}
	}
	for(int i=1000000-1;i>=2;i--){
		if(gap[i]==-1)gap[i]=pre;
		else{
			pre=gap[i];
			gap[i]=0;
		}
	}
	gap[2]=gap[1]=gap[0]=0;
	int k;
	while(cin>>k,k)cout<<gap[k]<<endl;
	return 0;
}

C++: #include <iostream>
#include <vector>
using namespace std;

vector<bool> Eratos(1299710,true);

int main()
{
	int N,min,max;
	for (int i = 2; i < 1142;) {
		for (int j = i * 2; j <= 1299710; j += i) {
			if (j % i == 0) {
				Eratos[j] = false;
			}
		}
		for (i++;!Eratos[i];i++);
	}
	while (cin >> N, N) {
		for (min = N; !Eratos[min]; min--);
		for (max = N; !Eratos[max]; max++);
		cout << max - min << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define N 1299709

int main(void){
	vector<bool> isprime(N+1);
	for(int i=0;i<isprime.size();i++) isprime[i]=true;
	int upto = (int)sqrt(isprime.size());
	isprime[1]=false;
	for(int i=2;i<=upto;++i){
		if(isprime[i]){//消されてなければその倍数を消す
			for(int j=2;i*j<isprime.size();++j) isprime[i*j] = false;
		}
	}
	int n;
	while(cin>>n,n){
		int min=2,max=N;
		for(int i=0;n-i>1;++i) if(isprime[n-i]){min=n-i;break;}
		for(int i=0;n+i<=N;++i) if(isprime[n+i]){max=n+i;break;}
		cout<<max-min<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <algorithm>
using namespace std;
#define N 2000000
bool prime[N+1];
int main(){
  for(int i=2;i<=N;++i) prime[i]=true;
  for(int i=2;i<=N;++i) if(prime[i]) for(int j=2;i*j<=N;++j) prime[i*j]=false;

  int k;
  while(cin>>k,k){
    int m=k,M=k;
    while(!prime[m]) --m;
    while(!prime[M]) ++M;
    cout << M-m << endl;
  }
  return 0;
}