Problem:
Twin Prime Prime numbers are widely applied for cryptographic and communication technology.
A twin prime is a prime number that differs from another prime number by 2.
For example, (5, 7) and (11, 13) are twin prime pairs. In this problem, we call the greater number of a twin prime "size of the twin prime." Your task is to create a program which reads an integer n and prints a twin prime which has the maximum size among twin primes less than or equals to n  You may assume that 5 ≤ n ≤ 10000. Input The input is a sequence of datasets. The end of the input is indicated by a line containing one zero. Each dataset is formatted as follows:  n (integer) Output For each dataset, print the twin prime p and q ( p < q ). p and q should be separated by a single space. Sample Input 12
100
200
300
0 Output for the Sample Input 5 7
71 73
197 199
281 283

Solution (Python):
def prime(m):
  N = range(1,m+2, 2)
  r = int(m**.5)
  h = len(N)
  N[0] = 0
  for i in range(h):
    x = N[i]
    if x>r: break
    if x and i+x<h: N[i+x:h:x]=[0] * ((h-1-i-x)/x+1)
  N[0] = 2
  return filter(None, N)

P = prime(10000)
x = [a for a,b in zip(P[1:],P[:-2]) if a-b==2]
while 1:
  n = input()
  if n==0: break
  for e in x:
    if e>n: break
    a = e
  print a-2,a

Solution (Python):
import bisect as bs
def prime(m):
  N = range(1,m+1, 2)
  N[0] = 2
  for i in range(1, int(m**.5)+1):
    x = N[i]
    if x: N[i+x::x] = [0] * len(N[i+x::x])
  return filter(None, N)

P = prime(10000)
x = [P[i] for i in range(1,len(P)) if P[i] - P[i-1]==2]
while 1:
  n = input()
  if n==0: break
  a = x[bs.bisect_right(x, n)-1]
  print a-2, a

Solution (Python):
import bisect as bs
def prime(m):
  N = range(1,m+1, 2)
  N[0] = 2
  for i in range(1, int(m**.5)+1):
    x = N[i]
    if x: N[i+x::x] = [0] * len(N[i+x::x])
  return filter(None, N)

P = prime(10000)
x = [a for a,b in zip(P[1:],P[:-1]) if a-b==2]
while 1:
  n = input()
  if n==0: break
  a = x[bs.bisect_right(x, n)-1]
  print a-2, a

Solution (Python):
import bisect as bs
def prime(m):
  N = range(1,m+1, 2)
  N[0] = 2
  n = len(N)
  for i in range(1, n):
    x = N[i]
    if x: N[i+x::x] = [0]*len(N[i+x::x])
  return filter(None, N)

P = prime(10000)
x = []
a = P[0]
for b in P[1:]:
  if b-a==2: x.append(b)
  a=b
while 1:
  n = int(raw_input())
  if n==0: break
  a = x[bs.bisect_right(x, n)-1]
  print a-2, a

Solution (Python):
import bisect as bs
def prime(m):
  N = range(1,m+1, 2)
  N[0] = 2
  for i in range(1, len(N)):
    x = N[i]
    if x: N[i+x::x] = [0]*len(N[i+x::x])
  return filter(None, N)
 
P = prime(10000)
x = []
a = P[0]
for b in P[1:]:
  if b-a==2: x.append(b)
  a=b
while 1:
  n = int(raw_input())
  if n==0: break
  a = x[bs.bisect_right(x, n)-1]
  print a-2, a

Solution (Python):
import bisect as bs
def prime(m):
  N = range(1,m+1, 2)
  N[0] = 2
  for i in range(1, len(N)):
    x = N[i]
    if x: N[i+x::x] = [0]*len(N[i+x::x])
  return filter(None, N)
 
P = prime(10000)
x = []
a = P[0]
x = [a for a,b in zip(P[1:],P[:-1]) if a-b==2]
while 1:
  n = int(raw_input())
  if n==0: break
  a = x[bs.bisect_right(x, n)-1]
  print a-2, a

Solution (Python):
n=1000000
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

while 1:
    n=int(input())
    if n==0: break
    for i in range(n,2,-1):
        if (p[i],p[i-2])==(1,1):
            print(i-2,i)
            break

Solution (Python):
primes = [0, 0] + [1]*9999
for i in range(2, 100):
    for j in range(i*i, 10001, i):
        primes[j] = 0

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

Solution (Python):

"""
"""
import sys
from sys import stdin
from bisect import bisect_right
input = stdin.readline


def create_prime_list(limit):
    """ ??¨??????????????????????????§limit?????§????´???°?????????????±???????
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def main(args):
    
    primes = create_prime_list(10000)
    twin_primes = []
    prev = primes[0]
    for p in primes[1:]:
        if p == prev + 2:
            twin_primes.append([prev, p])
        prev = p

    keys = [x[1] for x in twin_primes]
    while True:
        n = int(input())
        if n == 0:
            break
        r = bisect_right(keys, n)
        print(*twin_primes[r-1])


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
"""
import sys
from sys import stdin
from bisect import bisect_right
input = stdin.readline


def create_prime_list(limit):
    """ ??¨??????????????????????????§limit?????§????´???°?????????????±???????
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def main(args):
    
    primes = create_prime_list(10000)
    twin_primes = []


    
    
    
    
    
    
    
    
    
    
    
    
    

    prev = primes[0]
    for p in primes[1:]:
         if p == prev + 2:
             twin_primes.append(p)
         prev = p

    while True:
        n = int(input())
        if n == 0:
            break
        r = bisect_right(twin_primes, n)
        print(twin_primes[r-1]-2, twin_primes[r-1])



if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):


import sys, math, os, bisect


PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def primes2(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

primes = primes2(10050)

while True:
    n = int(input())
    if n == 0:
        break
    idx = bisect.bisect_left(primes, n)
    while True:
        
        
        if primes[idx] > n:
            idx -= 1
        if primes[idx] - primes[idx - 1] == 2:
            print(primes[idx - 1], primes[idx])
            break
        idx -= 1

Solution (Python):
import math

MAX = 10000


def is_prime_number(num):
    for divisor in range(3, int(math.sqrt(num) + 1), 2):
        if num % divisor == 0:
            return False

    return True


def create_prime_number_list(max):
    prime_number_list = list(range(0, max + 1))

    prime_number_list[0] = False
    prime_number_list[1] = False

    for index in range(2 * 2, max + 1, 2):
        prime_number_list[index] = False

    for num in range(3, int(math.sqrt(max + 1)), 2):

        if is_prime_number(num):
            for index in range(num * 2, max + 1, num):
                prime_number_list[index] = False

    return prime_number_list


prime_number_list = create_prime_number_list(MAX)
output = []

while True:

    num = int(input())

    if num == 0:
        break

    if num % 2 == 0:
        num -= 1

    for index in range(num, 0, -2):
        if prime_number_list[index - 2] and prime_number_list[index]:
            output.append(str(index - 2) + " " + str(index))
            break

print("\n".join(output))

Solution (Python):
import math
m = 10000
s = [1 for i in range(m+1)]
s[0] = 0
for i in range(2, int(math.sqrt(m))+1):
    if s[i] != 0:
        for j in range(i*2, m, i):
            s[j] = 0

ss = []
for i in range(m+1):
    if s[i] == 1:
      ss.append(i)
ss.reverse()

while True:
    n = int(input())
    if n == 0:
        quit()
    for i in range(len(ss)):
        if ss[i] <= n and ss[i] - ss[i+1] == 2:
            print(ss[i+1], ss[i])
            break

Solution (Python):
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

MAX = 10001
primes = list()
for i in range(MAX):
    primes.append(True)
primes[0] = False
primes[1] = False

tprimes = [False for i in range(MAX)]

for i in range(2, MAX):
    j = i + i
    while j < MAX:
        primes[j] = False
        j = j + i

for i in range(2, MAX):
    if primes[i] and primes[i-2]:
        tprimes[i] = True

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

    for i in range(n, -1, -1):
        if tprimes[i]:
            print(i-2, i)
            break

Solution (Python):



MAX = 10000
SQRT = 100     

prime = [True for i in range(MAX)]
def sieve():
	for i in range(4, MAX, 2):
		prime[i] = False
	for i in range(3, SQRT, 2):
		if prime[i] is True:
			for j in range(i*i, MAX, i):
				prime[j] = False
sieve()
while True:
	n = int(input())
	if n == 0: break
	if (n & 1) == 0: n -= 1
	while not prime[n] or not prime[n - 2]: n -= 2
	print(n-2, n)

Solution (Python):



MAX = 10001
SQRT = 100     

prime = [True for i in range(MAX)]
def sieve():
	for i in range(4, MAX, 2):
		prime[i] = False
	for i in range(3, SQRT, 2):
		if prime[i] is True:
			for j in range(i*i, MAX, i):
				prime[j] = False
sieve()
tbl = [0]*MAX
ans = 0
for i in range(5, MAX, 2):
	if prime[i] and prime[i-2]: ans = i
	tbl[i] = ans
	
while True:
	n = int(input())
	if n == 0: break
	if (n & 1) == 0: n -= 1
	print(tbl[n]-2, tbl[n])

Solution (Python):



MAX = 10001
SQRT = 100     

prime = [True]*MAX
def sieve():


	for i in range(3, SQRT, 2):
		if prime[i] is True:
			for j in range(i*i, MAX, i):
				prime[j] = False
sieve()
tbl, ans = [0]*MAX, 0
for i in range(5, MAX, 2):
	if prime[i] and prime[i-2]: ans = i
	tbl[i] = ans
	
while True:
	n = int(input())
	if n == 0: break
	if (n & 1) == 0: n -= 1
	print(tbl[n]-2, tbl[n])

Solution (Python):
def primes(n):
  tf = [True] * (n + 1)
  tf[0] = tf[1] = False
  for i in range(2, int(n ** (1 / 2)) + 1):
    if tf[i]:
      for j in range(i ** 2, n + 1, i):
        tf[j] = False
  return [i for i in range(n + 1) if tf[i]]

def add_twin(prime_lst, twin_lst):
  prime_lst2 = prime_lst[1:]
  for x, y in zip(prime_lst, prime_lst2):
    if y - x == 2:
      twin_lst.append(y)

def search_twin(x, twin_lst):
  left = 0
  right = len(twin_lst)
  while left + 1 < right:
    mid = (left + right) // 2
    if twin_lst[mid] > x:
      right = mid
    elif twin_lst[mid] < x:
      left = mid
    else:
      return x
  return twin_lst[left]

prime_lst = primes(10000)
twin_lst = []
add_twin(prime_lst, twin_lst)

while True:
  n = int(input())
  if n == 0:
    break
  a = search_twin(n, twin_lst)
  print(a - 2, a)

Solution (Python):
import math
N=10000
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
    for i in range(n,2,-1):
        if prime[i]==prime[i-2]==1:
            print i-2,i
            break

Solution (Python):
from bisect import bisect
MAXN = 10000
P = [True]*MAXN
P[0] = P[1] = False
for i in xrange(int(MAXN**0.5)+1):
    if P[i]:
        for j in xrange(i+i,MAXN,i):
            P[j] = False
TP = filter(lambda i:P[i] and P[i-2], xrange(2,MAXN))
while True:
    n = int(raw_input())
    if n == 0:
        break
    m = TP[bisect(TP,n)-1]
    print m-2, m

Solution (Python):
M = 10**4+1
p = [1]*M; a = [0,0]; prm = 0
p[0],p[1] = 0,0
for i in xrange(2,M):
    if p[i]:
        if p[i-2]: prm = i
        for j in xrange(i*i,M,i):
            p[j] = 0
    a.append(prm)
while 1:
    n = input()
    if n==0: break
    print a[n]-2,a[n]

Solution (Python):
r = 10001
sqrt = int(r**0.5)
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
	if p[i]:
		p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

while True:
	n = int(raw_input())
	if n == 0: break
	for i in range(n,1,-1):
		if p[i-1] and p[i-3]:
			print i-2,i
			break

Solution (Python):
r = 10001
sqrt = int(r**0.5)
p = [1]*r
twin = [0]*r
p[0] = 0
p[1::2] = [0 for x in range(1,r,2)]
for i in range(2,r,2):
	if p[i]:
		p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
		if p[i-2]:
			twin[i] = 1
		
while True:
	n = int(raw_input())
	if n == 0: break
	i = n - twin[:n][::-1].index(1)
	print i-2,i

Solution (Python):
r = 10001
sqrt = int(r**0.5)
p = [1]*r
twin = [0]*r
p[0] = 0
p[1::2] = [0 for x in range(1,r,2)]
for i in range(2,r,2):
	if p[i]:
		p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
		if p[i-2]:
			twin[i:i+300] = [i+1 for x in range(i,i+300)]
		
while True:
	n = int(raw_input())
	if n == 0: break
	print twin[n-1]-2,twin[n-1]

Solution (Python):
r = 10001
sqrt = int(r**0.5)
p = [1]*r
twin = [0]*r
p[0] = 0
p[1::2] = [0 for x in range(1,r,2)]
for i in range(2,r,2):
	if p[i]:
		p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
		if p[i-2]:
			twin[i:i+250] = [i+1 for x in range(i,i+250)]
		
while True:
	n = int(raw_input())
	if n == 0: break
	print twin[n-1]-2,twin[n-1]

Solution (Python):
r = 10001
sqrt = int(r**0.5)
p = [1]*r
twin = [0]*r
p[0] = 0
p[1::2] = [0 for x in range(1,r,2)]
for i in range(2,r,2):
	if p[i]:
		p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
		if p[i-2]:
			twin[i:i+250] = [i+1 for x in range(i,i+250)]
		
while True:
	n = int(raw_input())
	if n == 0: break
	print twin[n-1]-2,twin[n-1]

Solution (Python):
MN = 10000
tp = []
op = -5
mem = [False * 2] + [True] * MN
for i in range(2, MN):
  if not mem[i]:
    continue
  if i - op == 2:
    tp.append((op, i))
  op = i
  for j in range(i + i, MN, i):
    mem[j] = False
tp.append((MN + 1, MN + 1))
while True:
  N = input()
  if not N:
    break
  for i, p in enumerate(tp):
    if p[1] > N:
      print('%d %d' % (tp[i - 1][0], tp[i - 1][1]))
      break

Solution (Python):
P = []
for n in range(10000):
    p = 3
    c = 0
    if n % 2 == 0:
        c += 1
    else:
        while p < int(n**0.5) + 1:
            if n % p != 0:
                p += 2
            else:
                c += 1
                break
    if c == 0:
        P.append(n)

P.reverse()

while 1:
        j = 0
        n = int(input())
        if n == 0:
            break
        else:
            for i in range(len(P)):
                if n >= P[i]:
                    j = i
                    break
            while 1:
                if P[j]-2 == P[j+1]:
                    print(P[j+1],P[j])
                    break
                else:
                    j += 1

Solution (Python):
import math

isPrime = [True] * 10001
primes = []
def eratos(n):
    isPrime[0] = isPrime[1] = False
    for i in range(2,int(math.sqrt(n))):
        if isPrime[i]:
            j = 2 * i
            while j <= n:
                isPrime[j] = False
                j = j + i
    for i in range(2,10000):
        if isPrime[i]:
            primes.append(i)
eratos(10000)

while True:
    try:
        n = int(input())
        if n == 0:
            break
        for i in range(n,2,-1):
            if isPrime[i]:
                if isPrime[i - 2]:
                    print(i - 2,i)
                    break
    except EOFError:
        break

Solution (Python):
def prime(N):
    first=[True for i in range(N+1)]
    first[0],first[1]=False,False
    for i in range(2,int((N+1)**0.5)):
        if not first[i]:continue
        for j in range(i*2,N+1,i):first[j]=False
    return [i for i in range(N+1) if first[i]]

prime_number=prime(10000)
while 1:
    n=int(input())
    if n==0:break
    box=0
    for i,j in enumerate(prime_number):
        if j>n:break
        if prime_number[i]-prime_number[i-1]==2:
            box=max(box,prime_number[i])
    print(box-2,box)

Solution (Python):
dplist = [(5, 3), (7, 5), (13, 11), (19, 17), (31, 29), (43, 41), (61, 59), (73, 71), (103, 101), (109, 107), (139, 137), (151, 149), (181, 179), (193, 191), (199, 197), (229, 227), (241, 239), (271, 269), (283, 281), (313, 311), (349, 347), (421, 419), (433, 431), (463, 461), (523, 521), (571, 569), (601, 599), (619, 617), (643, 641), (661, 659), (811, 809), (823, 821), (829, 827), (859, 857), (883, 881), (1021, 1019), (1033, 1031), (1051, 1049), (1063, 1061), (1093, 1091), (1153, 1151), (1231, 1229), (1279, 1277), (1291, 1289), (1303, 1301), (1321, 1319), (1429, 1427), (1453, 1451), (1483, 1481), (1489, 1487), (1609, 1607), (1621, 1619), (1669, 1667), (1699, 1697), (1723, 1721), (1789, 1787), (1873, 1871), (1879, 1877), (1933, 1931), (1951, 1949), (1999, 1997), (2029, 2027), (2083, 2081), (2089, 2087), (2113, 2111), (2131, 2129), (2143, 2141), (2239, 2237), (2269, 2267), (2311, 2309), (2341, 2339), (2383, 2381), (2551, 2549), (2593, 2591), (2659, 2657), (2689, 2687), (2713, 2711), (2731, 2729), (2791, 2789), (2803, 2801), (2971, 2969), (3001, 2999), (3121, 3119), (3169, 3167), (3253, 3251), (3259, 3257), (3301, 3299), (3331, 3329), (3361, 3359), (3373, 3371), (3391, 3389), (3463, 3461), (3469, 3467), (3529, 3527), (3541, 3539), (3559, 3557), (3583, 3581), (3673, 3671), (3769, 3767), (3823, 3821), (3853, 3851), (3919, 3917), (3931, 3929), (4003, 4001), (4021, 4019), (4051, 4049), (4093, 4091), (4129, 4127), (4159, 4157), (4219, 4217), (4231, 4229), (4243, 4241), (4261, 4259), (4273, 4271), (4339, 4337), (4423, 4421), (4483, 4481), (4519, 4517), (4549, 4547), (4639, 4637), (4651, 4649), (4723, 4721), (4789, 4787), (4801, 4799), (4933, 4931), (4969, 4967), (5011, 5009), (5023, 5021), (5101, 5099), (5233, 5231), (5281, 5279), (5419, 5417), (5443, 5441), (5479, 5477), (5503, 5501), (5521, 5519), (5641, 5639), (5653, 5651), (5659, 5657), (5743, 5741), (5851, 5849), (5869, 5867), (5881, 5879), (6091, 6089), (6133, 6131), (6199, 6197), (6271, 6269), (6301, 6299), (6361, 6359), (6451, 6449), (6553, 6551), (6571, 6569), (6661, 6659), (6691, 6689), (6703, 6701), (6763, 6761), (6781, 6779), (6793, 6791), (6829, 6827), (6871, 6869), (6949, 6947), (6961, 6959), (7129, 7127), (7213, 7211), (7309, 7307), (7333, 7331), (7351, 7349), (7459, 7457), (7489, 7487), (7549, 7547), (7561, 7559), (7591, 7589), (7759, 7757), (7879, 7877), (7951, 7949), (8011, 8009), (8089, 8087), (8221, 8219), (8233, 8231), (8293, 8291), (8389, 8387), (8431, 8429), (8539, 8537), (8599, 8597), (8629, 8627), (8821, 8819), (8839, 8837), (8863, 8861), (8971, 8969), (9001, 8999), (9013, 9011), (9043, 9041), (9241, 9239), (9283, 9281), (9343, 9341), (9421, 9419), (9433, 9431), (9439, 9437), (9463, 9461), (9631, 9629), (9679, 9677), (9721, 9719), (9769, 9767), (9859, 9857), (9931, 9929)]

while(True):
    N = int(input())
    if N == 0:
        break
    for i in range(len(dplist)-1, -1, -1):
        if dplist[i][0] <= N:
            print(dplist[i][1], dplist[i][0])
            break

Solution (Python):
import math


def prime(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    else:
        return True


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

    if n % 2 == 0:
        n -= 1

    for i in range(n, 3, -2):
        if prime(i) and prime(i-2):
            print(i-2, i)
            break

Solution (Python):
def isPrime(n):
    for i in range(2,int(n**.5+1)):
        if n%i==0:
            return False
    return True
while 1:
    n=int(input())
    if not n:break
    for i in range(n,1,-1):
        if isPrime(i) and isPrime(i-2):
            print(i-2,i)
            break