Problem:


Problem B: Prime Gap

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

10
11
27
2
492170
0

Output for the Sample Input

4
0
6
0
114



Sample input:
10
11
27
2
492170
0


Sample output:
4
0
6
0
114

Submission status: Accepted

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

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        prime = self.sieve(1299709)
        while True:
            n = input()
            if n == 0:
                break
            if prime[n]:
                print 0
            else:
                lower = upper = n
                while not prime[lower]:
                    lower -= 1
                while not prime[upper]:
                    upper += 1
                print upper - lower
        
        return None

    def sieve(self, n):
        f = [True for i in xrange(n+1)]
        f[0] = False
        f[1] = False
        i = 2
        while i * i <= n:
            if f[i]:
                j = 2
                while i * j <= n:
                    f[i * j] = False
                    j += 1
            i += 1
        return f


if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Accepted

Solution code:
#!/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 = k
        while primeTable[i] is False: i += 1
        j = i-1
        while primeTable[j] is False: j -= 1
        print(i-j)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
#! /usr/bin/python
# -*- coding: utf-8 -*-

def plen(prime, val, pos, left, right):
    if pos == len(prime)-1:
        if val == Max:
            return 0
        else:
            return prime[len(prime)-1]-prime[len(prime)-2]
    if prime[pos] == val:
        return 0
    elif prime[pos] < val < prime[pos+1]:
        return prime[pos+1]-prime[pos]
    else:
        if val < prime[pos]:
            return plen(prime, val, (pos+left)/2, left, pos)
        else:
            return plen(prime, val, (pos+right+1)/2, pos, right)

Max = 1299709
used = [True]*(Max+1)
used[0] = False
used[1] = False
for i in range(2, Max+1):
    if used[i] == True:
        for j in range(i+i, Max+1, i):
            used[j] = False

prime = []
for i in range(2, Max+1):
    if used[i] == True:
        prime.append(i)

#print prime
n = int(raw_input())
while n!=0:
    print plen(prime, n, len(prime)/2, 0, len(prime)-1)
    n = int(raw_input())

Submission status: Accepted

Solution code:
#!/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()

Submission status: Accepted

Solution code:
n=1299709
p=[1]*(n+1)
p[0],p[1]=0,0
for i in range(2,int(n**0.5)+1):
    if p[i]:        
        for j in range(i*i,n+1,i):
            p[j]=0
#p=[i for i in range(n+1) if p[i]==1]
while 1:
    n=int(input())
    if n==0:break
    if p[n]:
        print(0)
        continue
    i=n
    while p[i] is 0:i-=1
    j=i+1
    while p[j] is 0:j+=1
    print(j-i)

Submission status: Accepted

Solution code:
primes = [0, 0] + 1299709*[1]
for i in range(2, 1141):
    if primes[i]:
        for j in range(i*i, 1299710, i):
            primes[j] = 0
while True:
    n = int(input())
    if n == 0:
        break
    if primes[n]:
        print(0)
        continue
    a = b = n
    while not primes[a]:
        a -= 1
    while not primes[b]:
        b += 1
    print(b-a)

Submission status: Accepted

Solution code:
import bisect
MAXN = 1300000
primes = []
sieve = [0,0] + [1] * MAXN
n = 2
while n*n < MAXN:
    if sieve[n]:
        primes.append(n)
        for m in range(2*n,MAXN,n):
            sieve[m] = 0
    n += 1
for m in range(n,MAXN):
    if sieve[m]:
        primes.append(m)

while True:
    N = int(input())
    if N == 0: break
    l = bisect.bisect_left(primes,N)
    r = bisect.bisect_right(primes,N)
    if r-l == 1:
        print(0)
    else:
        print(primes[l] - primes[l-1])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False

    def is_prime(self, n):
        return self.A[n]

def main():
    rr = []
    pr = Prime(1299709**2)

    while True:
        n = I()
        if n == 0:
            break
        l = r = n
        while not pr.is_prime(l):
            l -= 1
        while not pr.is_prime(r):
            r += 1
        rr.append(r-l)

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import sys
import bisect

MAX = 1299710
prime = [-1] * MAX
prime_list = []
i = 2
while MAX > i:
	if prime[i - 1] == -1:
		prime[i - 1] = 0
		temp = i * 2
		prime_list.append(i)
		while temp < MAX:
			prime[temp - 1] = 1
			temp += i
	if i == 2:
		i += 1
	else:
		i += 2

while True:
    n = int(sys.stdin.readline())
    
    if n == 0:
        break
    
    start = bisect.bisect_left(prime_list, n)
    end = bisect.bisect_right(prime_list, n)
    if prime_list[start] == n:
        print 0
    else:
        print prime_list[end] - prime_list[start - 1]

Submission status: Accepted

Solution code:
import math
N=1299709
prime=[1]*(N+1)
prime[0],prime[1]=0,0
for i in range(2,int(math.sqrt(N))):
    if prime[i]==1:
        j=i
        while i*j<=N:
            prime[i*j]=0
            j+=1

while True:
    n=input()
    if n==0:break
    if prime[n]==1:
        print 0
    else:
        i=n-1
        while prime[i]!=1:
            i-=1
        j=n+1
        while prime[j]!=1:
            j+=1
        print j-i

Submission status: Accepted

Solution code:
M = 1299710
isPrime = [1]*M
isPrime[0],isPrime[1] = 0,0
lp = [0]*M; p = []
b = 2
for i in xrange(2,M):
    if isPrime[i]:
        for j in range(i*i,M,i):
            isPrime[j] = 0
        p.append(i)
        b = i
    lp[i] = b
while 1:
    n = input()
    if n==0: break
    print p[p.index(lp[n])+1]-lp[n] if lp[n]!=n else "0"

Submission status: Accepted

Solution code:
M = 1299710
isPrime = [1]*M
isPrime[0],isPrime[1] = 0,0
for i in xrange(2,M):
    if isPrime[i]:
        for j in range(i*i,M,i):
            isPrime[j] = 0
while 1:
    n = input()
    if n==0: break
    p = q = n
    if isPrime[n]:
        print 0
    else:
        while isPrime[p]==0:p-=1
        while isPrime[q]==0:q+=1
        print q-p

Submission status: Accepted

Solution code:
r = 1299710
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]

while 1:
	n = input()
	if n == 0: break
	l = r = n
	while p[l] == 0: l -= 1
	while p[r] == 0: r += 1
	print r - l

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
M = 1500000
l = [1]*(M+1)
p = 2
prime = []
while p <= M:
    while p <= M and not l[p]:
        p += 1
    j = p
    while j <= M:
        l[j] = 0
        j += p
    prime.append(p)
    
def solve(k):
    i = bisect.bisect_left(prime,k)
    if prime[i] == k:
        print(0)
    else:
        print(prime[i] - prime[i-1])
    return

#Solve
if __name__ == "__main__":
    while 1:
        k = I()
        if k == 0:
            break
        solve(k)

Submission status: Accepted

Solution code:
# 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)

Submission status: Runtime Error

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

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        prime = self.sieve(1299709)
        while True:
            n = input()
            if prime[n]:
                print 0
            else:
                lower = upper = n
                while not prime[lower]:
                    lower -= 1
                while not prime[upper]:
                    upper += 1
                print upper - lower
        
        return None

    def sieve(self, n):
        f = [True for i in xrange(n+1)]
        f[0] = False
        f[1] = False
        i = 2
        while i * i <= n:
            if f[i]:
                j = 2
                while i * j <= n:
                    f[i * j] = False
                    j += 1
            i += 1
        return f


if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Runtime Error

Solution code:
#!/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)

Submission status: Runtime Error

Solution code:
#!/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)