Problem:


四つ子素数

  (a, a+2, a+6, a+8) のように並んだ 4 つの素数の組を四つ子素数といいます。四つ子素数を構成する四つの素数のうち、最大の数をその四つ子素数の大きさと呼びます。例えば、最も小さい大きさの四つ子素数は、(5, 7, 11, 13) の組であり、その大きさは 13 です。次に大きい四つ子素数は、(11, 13, 17, 19) の組で、その大きさは 19 です。

  整数 n (13 ≤ n ≤ 10,000,000) を入力とし、大きさが n 以下になるような四つ子素数のうち、最大となるものの大きさを出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットとして１つの整数 n が１行に与えられます。

データセットの数は 2000 を超えません。

Output

入力データセットごとに、最大となる四つ子素数の大きさを1行に出力します。

Sample Input

13
14
15
16
17
18
19
20
10000
0

Output for the Sample Input

13
13
13
13
13
13
19
19
9439



Sample input:
13
14
15
16
17
18
19
20
10000
0


Sample output:
13
13
13
13
13
13
19
19
9439

Submission status: Accepted

Solution code:
from bisect import bisect
M = 10**7+1
p = [1]*M
p[0] = p[1] = 0
for i in range(2, int(M**.5)+1):
    if p[i]:
        p[i*i:M:i] = (0 for i in range(i*i, M, i))
B = [13]
for x in range(19, M, 10):
    if p[x-8] and p[x-6] and p[x-2] and p[x]:
        B.append(x)

while 1:
    N = int(input())
    if N == 0:
        break
    print(B[bisect(B, N)-1])

Submission status: Accepted

Solution code:
from bisect import bisect_right as br

def quad_primes(n):
  is_prime = [True] * (n + 1)
  is_prime[0] = is_prime[1] = False
  for i in range(2, int(n ** (1 / 2)) + 1):
    if is_prime[i]:
      for j in range(i * i, n + 1, i):
        is_prime[j] = False

  return [i + 8 for i in range(n - 7) if is_prime[i] and is_prime[i + 2] and is_prime[i + 6] and is_prime[i + 8]]

quad = quad_primes(10000000)

while True:
  n = int(input())
  if n == 0:
    break
  print(quad[br(quad, n) - 1])

Submission status: Runtime Error

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1
if __name__ == "__main__":
    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            for x in xrange(n, 13, -1):
                if (is_prime(x) and is_prime(x - 2) and is_prime(x - 6) and is_prime(x - 8)):
                    print x
                    break

Submission status: Runtime Error

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1
if __name__ == "__main__":
    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            tmp = (n - 19) / 30
            while tmp >= 0:
                x = 30 * tmp + 19
                if (is_prime(x) and is_prime(x - 2) and is_prime(x - 6) and is_prime(x - 8)):
                    print x
                    break
                tmp -= 1

Submission status: Runtime Error

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1
    
if __name__ == "__main__":
    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            tmp = (n - 19) / 30
            while tmp >= 0:
                x = 30 * tmp + 19
                if (is_prime(x) and is_prime(x - 2) and is_prime(x - 6) and is_prime(x - 8)):
                    print x
                    break
                tmp -= 1

Submission status: Runtime Error

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1
    
if __name__ == "__main__":
    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            tmp = int((n - 19) / 30)
            while tmp >= 0:
                x = 30 * tmp + 19
                if (is_prime(x) and is_prime(x - 2) and is_prime(x - 6) and is_prime(x - 8)):
                    print x
                    break
                tmp -= 1

Submission status: Runtime Error

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1
    
if __name__ == "__main__":
    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            tmp = int((n - 19) / 30)
            if tmp == 0:
                print 19
            while tmp > 0:
                x = 30 * tmp + 19
                if (is_prime(x) and is_prime(x - 2) and is_prime(x - 6) and is_prime(x - 8)):
                    print x
                    break
                tmp -= 1

Submission status: Runtime Error

Solution code:
import sys

def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1
    
if __name__ == "__main__":
    sys.setrecursionlimit(1145)
    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            tmp = int((n - 19) / 30)
            if tmp == 0:
                print 19
            while tmp > 0:
                x = 30 * tmp + 19
                if (is_prime(x) and is_prime(x - 2) and is_prime(x - 6) and is_prime(x - 8)):
                    print x
                    break
                tmp -= 1

Submission status: Runtime Error

Solution code:
import sys

def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1
    
if __name__ == "__main__":
    sys.setrecursionlimit(1000)
    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            tmp = int((n - 19) / 30)
            if tmp == 0:
                print 19
            while tmp > 0:
                x = 30 * tmp + 19
                if (is_prime(x) and is_prime(x - 2) and is_prime(x - 6) and is_prime(x - 8)):
                    print x
                    break
                tmp -= 1

Submission status: Runtime Error

Solution code:
import sys
def is_prime2(q,k=100):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    for i in xrange(3,k):
        x,y = q,i
        while y:
            x, y =  y, x % y
        if x != 1: continue
        if pow(i, q-1, q) != 1:
            return False
    return True
if __name__ == "__main__":

    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            tmp = int((n - 19) / 30)
            if tmp == 0:
                print 19
            while tmp > 0:
                x = 30 * tmp + 19
                if (is_prime2(x) and is_prime2(x - 2) and is_prime2(x - 6) and is_prime2(x - 8)):
                    print x
                    break
                tmp -= 1

Submission status: Runtime Error

Solution code:
import sys
def is_prime2(q,k=100):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    for i in xrange(3,k):
        x,y = q,i
        while y:
            x, y =  y, x % y
        if x != 1: continue
        if pow(i, q-1, q) != 1:
            return False
    return True
if __name__ == "__main__":

    while True:
        n = input()
        if (n == 0):
            break
        if (n < 19):
            print 13
        else:
            tmp = int((n - 19) / 30)
            if tmp == 0:
                print 19
            while tmp > 0:
                x = 30 * tmp + 19
                if (is_prime2(x) and is_prime2(x - 2) and is_prime2(x - 6) and is_prime2(x - 8)):
                    print x
                    break
                tmp -= 1
                break

Submission status: Runtime Error

Solution code:

def is_prime2(q,k=100):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    for i in xrange(3,k):
        x,y = q,i
        while y:
            x, y =  y, x % y
        if x != 1: continue
        if pow(i, q-1, q) != 1:
            return False
    return True

while True:
    n = input()
    if (n == 0):
        break
    if (n < 19):
        print 13
    else:
        tmp = int((n - 19) / 30)
        while tmp > 0:
            x = 30 * tmp + 19
            if (is_prime2(x) and is_prime2(x - 2) and is_prime2(x - 6) and is_prime2(x - 8)):
                print x
                break
            tmp -= 1

Submission status: Runtime Error

Solution code:

def is_prime2(q,k=100):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    for i in xrange(3,k):
        x,y = q,i
        while y:
            x, y =  y, x % y
        if x != 1: continue
        if pow(i, q-1, q) != 1:
            return False
    return True

while True:
    n = input()
    if (n == 0):
        break
    if (n < 19):
        print 13
    else:
        tmp = int((n - 19) / 30)
        while tmp > 0:
            x = 30 * tmp + 19
            if (is_prime2(x) and is_prime2(x - 2) and is_prime2(x - 6) and is_prime2(x - 8)):
                print x
                break
            tmp -= 1

Submission status: Runtime Error

Solution code:
MAX_N = 10000000+1

def make_sosu_tbl():
    for i in range(2, MAX_N):
        if sos[i]:
            for j in range(i+i, MAX_N+1, i):
                sos[j] = 0
        if i**2 >= MAX_N:break

sos = [1] * (MAX_N+1)
make_sosu_tbl()
while 1:
#    MAX_N = int(input())
#    if not MAX_N: break
#    
    n = int(input())
    for i in reversed(range(13,n+1)):
        if sos[i] and sos[i-2] and sos[i-6] and sos[i-8]:
            print(i)
            break

Submission status: Runtime Error

Solution code:
MAX_N = 10000000+1

def make_sosu_tbl():
    for i in range(2, MAX_N):
        if sos[i]:
            for j in range(i+i, MAX_N+1, i):
                sos[j] = 0
        if i**2 >= MAX_N:break

sos = [1] * (MAX_N+1)
make_sosu_tbl()
while 1:
#    MAX_N = int(input())
#    if not MAX_N: break
#    
    n = int(input())
    if not n:break
    for i in reversed(range(13,n+1)):
        if sos[i] and sos[i-2] and sos[i-6] and sos[i-8]:
            print(i)
            break

Submission status: Runtime Error

Solution code:
MAX_N = 10000000+1

def make_sosu_tbl():
    for i in range(2, MAX_N):
        if sos[i]:
            for j in range(i+i, MAX_N+1, i):
                sos[j] = 0
        if i**2 >= MAX_N:break

sos = [1] * (MAX_N+1)
make_sosu_tbl()
while 1:
    n = int(input())
    if not n: break
    for i in reversed(range(13, n+1)):
        if sos[i] and sos[i-2] and sos[i-6] and sos[i-8]:
            print(i)
            break

Submission status: Runtime Error

Solution code:
move = [[[10, 10], [4, 4]], [[8, 2],[4, 2]]]

MAX_N = 10000000+1
sos = [1] * (MAX_N+1)
sos[0] = sos[1] = 0
for i in range(2, int(MAX_N**0.5)+1):
    if sos[i]:
        for j in range(i+i, MAX_N+1, i):
            sos[j] = 0

while 1:
    n = int(input())

    if not n: break
    n -= (n%2 == 0)
    while n >= 13:
        if sos[n] and sos[n-2] and sos[n-6] and sos[n-8]:
            print(n)
            break
        else:
            n -= move[sos[n-8]][sos[n-6]][sos[n-2]]
# measure_stop = datetime.now()
# print(measure_stop - measure_start)

Submission status: Runtime Error

Solution code:
def sieve(n):
    p = [True] * (n + 1)
    p[0] = p[1] = False
    
    for i in range(int(n ** 0.5) + 1):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = False
    return p
def get_quad(n, p):
    for ni in range(n,0,-1):
        if p[ni] and p[ni - 2] and p[ni - 6] and p[ni - 8]:
            return ni
import sys
f = sys.stdin


n = [int(line) for line in f][:-1]
prime = sieve(max(n))
for ni in n:
    print(get_quad(ni, prime))

Submission status: Runtime Error

Solution code:
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5) + 1):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def get_quad(n, p):
    for ni in range(n,0,-1):
        if p[ni] and p[ni - 2] and p[ni - 6] and p[ni - 8]:
            return ni

import sys
f = sys.stdin


n = [int(line) for line in f][:-1]
prime = sieve(max(n))
for ni in n:
    print(get_quad(ni, prime))

Submission status: Runtime Error

Solution code:
def get_quad(n, p):
    for ni in range(n,0,-1):
        if p[ni] and p[ni - 2] and p[ni - 6] and p[ni - 8]:
            return ni
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5) + 1):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p
import sys
f = sys.stdin

n = []
while True:
    ni = int(f.readline())
    if ni == 0:
        break
    n.append(ni)

prime = sieve(max(n))
for ni in n:
    print(get_quad(ni, prime))

Submission status: Runtime Error

Solution code:
def get_quad(n, p):
    for ni in range(n,0,-1):
        if p[ni] and p[ni - 2] and p[ni - 6] and p[ni - 8]:
            return ni
        
def sieve():
    n = 10000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p
import sys
f = sys.stdin

prime = sieve()
while True:
    ni = int(f.readline())
    if ni == 0:
        break
    print(get_quad(ni, prime))

Submission status: Runtime Error

Solution code:
def get_quad(n, p):
    return 0
        
def sieve():
    n = 10000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p
import sys
f = sys.stdin

prime = sieve()
while True:
    ni = int(f.readline())
    if ni == 0:
        break
    print(get_quad(ni, prime))

Submission status: Runtime Error

Solution code:
def get_quad(n, p):
    return 0
        
def sieve():
    n = 10000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p
import sys
f = sys.stdin

prime = sieve()
while True:
    ni = int(f.readline())
    if ni == 0:
        break

Submission status: Runtime Error

Solution code:
def sieve():
    n = 10000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p
import sys
f = sys.stdin

prime = sieve()
while True:
    ni = int(input())
    if ni == 0:
        break

Submission status: Runtime Error

Solution code:

while True:
    ni = int(input())
    if ni == 0:
        break
    print('0')

Submission status: Runtime Error

Solution code:
def get_quad(n, p):
    if n < 19:
        return 13
    n = (n + 1) // 10 * 10 - 1
    for ni in range(n,0,-10):
        if p[ni] and p[ni - 2] and p[ni - 6] and p[ni - 8]:
            return ni
        
def sieve():
    n = 10000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

prime = sieve()
while True:
    n = f.readline().strip()
    if not n.isdigit():
        continue
    n = int(n)
    if n == 0:
        break
    print(get_quad(n, prime))

Submission status: Runtime Error

Solution code:
primes = [0, 0] + [1]*999999
for i in range(2, 1001):
    for j in range(i*i, 1000001, i):
        primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    for i in range(5, n+1)[::-1]:
        if primes[i] and primes[i-2] and primes[i-6] and primes[i-8]:
            print(i)
            break

Submission status: Runtime Error

Solution code:
primes = [0, 0] + [1] * 9999991
for i in range(2, 3163):
    for j in range(i*i, 9999992, i):
        if primes[j]:
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    while True:
        if primes[n-8] and primes[n-6] and primes[n-2] and primes[n]:
            print(n)
            break
        else:
            n -= 1

Submission status: Runtime Error

Solution code:
primes = [0, 0] + [1] * 9999999
for i in range(2, 3163):
    if primes[i]:
        for j in range(i*i, 10000001, i):
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    for i in range(5, n+1)[::-1]:
        if primes[i-8] & primes[i-6] & primes[i-2] & primes[i]):
            print(i)
            break

Submission status: Runtime Error

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

while 1:
	n = input()
	if n == 0: break
	for i in range(n-(1-n%2),12,-4):
		if p[i] and p[i-2] and p[i-6] and p[i-8]:
			print i
			break

Submission status: Runtime Error

Solution code:
def isP(n):
	for i in prime:
		if i >= n:
			break
		if n%i == 0:
			return False
	return True

r = int(10000001**0.5)
s = int(r**0.5)
p = [1]*r
p[0] = p[1] = 0
for i in range(2,s):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]
prime = []
for i in range(r):
	if p[i]:
		prime.append(i)

while 1:
	n = input()
	if n == 0: break
	i = n-(1-n%2)
	while i > 12:
		if not isP(i-8) or not isP(i-2):
			i -= 4
			continue
		if isP(i) and isP(i-6):
			print i
			break
		i -= 2

Submission status: Runtime Error

Solution code:
def isP(n):
	for i in prime:
		if i >= n:
			break
		if n%i == 0:
			return False
	return True

r = int(10000001**0.5)
s = int(r**0.5)
p = [1]*r
p[0] = p[1] = 0
for i in range(2,s):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]
prime = []
for i in range(r):
	if p[i]:
		prime.append(i)

while 1:
	n = input()
	if n == 0: break
	i = n-(1-n%2)
	while i > 12:
		p6 = isP(i-6)
		if not isP(i-8) or not isP(i-2):
			if not p6:
				i -= 10
			else:
				i -= 4
			continue
		if isP(i) and p6:
			print i
			break
		i -= 2

Submission status: Runtime Error

Solution code:
MAX = 10000000
def isP(n):
	for i in prime:
		if i >= n:
			break
		if n%i == 0:
			return False
	return True

r = int((MAX+1)**0.5)
s = int(r**0.5)
p = [1]*r
p[0] = p[1] = 0
for i in range(2,s):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]
prime = []
for i in range(r):
	if p[i]:
		prime.append(i)

while 1:
	n = input()
	if n == 0: break
	i = n-(1-n%2)
	while i > 12:
		p6 = isP(i-6)
		if not isP(i-8) or not isP(i-2):
			if not p6:
				i -= 10
			else:
				i -= 4
			continue
		if isP(i) and p6:
			print i
			break
		i -= 2

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	print n

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	print(n)

Submission status: Runtime Error

Solution code:
r =10000001
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 j in range(2*i,r,i)]
		
while 1:
	n = input()
	if n == 0: break
	n -= 1-n%2
	while any(not p[n-i] for i in [0,2,6,8]):
		n -= 2
	print n