Problem:


素数 II

素数というのは、1 よりも大きくそれ自身か 1 でしか割りきれない整数をいいます。例えば、2 は、2 と 1 でしか割り切れないので素数ですが、12 は、12 と 1 のほかに、2, 3, 4, 6 で割りきれる数なので素数ではありません。

整数 n を入力したとき、n より小さい素数のうち最も大きいものと、n より大きい素数のうち最も小さいものを出力するプログラムを作成してください。

Input

複数のデータセットが与えられます。各データセットに n (3 ≤ n ≤ 50,000) が１行に与えられます。

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

Output

各データセットに対して、n より小さい素数のうち最大のものと、n より大きい素数のうち最小のものを１つのスペースで区切って１行に出力して下さい。

Sample Input

19
3517

Output for the Sample Input

17 23
3511 3527



Sample input:
19
3517


Sample output:
17 23
3511 3527

Submission status: Accepted

Solution code:
import math
import sys
isPrime=[False, False]
for i in range(2,1000000):
    isPrime.append(True)
for i in range(2,int(math.sqrt(1000000))):
    if isPrime[i]:
        for j in range(i*i, 1000000, i):
            isPrime[j]=False
for l in sys.stdin:
    f=int(l)
    ans=[]
    while True:
        if isPrime[f-1]:
            ans.append(int(f-1))
            break
        else:
            f=f-1
    f=int(l)
    while True:
        if isPrime[f+1]:
            ans.append(int(f+1))
            break
        else: 
            f=f+1
    print("%d %d"%(ans[0],ans[1]))

Submission status: Accepted

Solution code:
is_prime = [False,False]

for i in range(2,1000000):
    is_prime.append(True)

for i in range(2,1000000):
    if is_prime[i]:
        for j in range(i*i,1000000,i):
            is_prime[j] = False

while 1:
    try:
        a = int(0)
        b = int(0)
        n = int(input())
        for i in range(n-1,0,-1):
            if is_prime[i]:
                a = i
                break
        
        for i in range(n+1,50022):
            if is_prime[i]:
                b = i
                break
                
        print("%s %d"%(a,b))
    except:
        break

Submission status: Accepted

Solution code:
check = [False,False]


for i in range(0,100000):
    check.append(True)

for i in range(2,100000):
    if(check[i]):
        for j in range(i*i,100000,i):
            check[j]=False


while True:
    try:
        x = int(input())
        a = b = x

        for i in reversed(range(0,x)):
            if(check[i]):
                a = i
                break

        while True:
            x += 1
            if(check[x]):
                b = x
                break
        
        print("%d %d"%(a,b))
        
    except:
        break

Submission status: Accepted

Solution code:
def main():
    is_prime = [i for i in range(1000000)]
    is_prime[0] = is_prime[1] = False

    for i in range(2, 1000000):
        is_prime[i] = True
    
    for i in range(2, 1000000):
        if i*i >= 1000000:
            break
        for j in range(i*i, 1000000, i):
            is_prime[j] = False
    
    while 1:
        try:
            ans = [0,0]
            n = int(input())
            for i in range(2,1000001):
                if is_prime[i]:
                    if i < n:
                        ans[0] = i
                    else:
                        if i != n:
                            ans[1] = i
                            break

            print('%s %d' % (ans[0],ans[1]))
        except:
            break

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    is_prime = [i for i in range(1000000)]
    is_prime[0] = is_prime[1] = False

    for i in range(2, 1000000):
        is_prime[i] = True
    
    for i in range(2, 1000000):
        if i*i >= 1000000:
            break
        for j in range(i*i, 1000000, i):
            is_prime[j] = False
    
    while 1:
        try:
            ans = [0,0]
            n = int(input())
            for i in range(2,1000001):
                if is_prime[i]:
                    if i < n:
                        ans[0] = i
                    else:
                        if i != n:
                            ans[1] = i
                            break

            print('%s %d' % (ans[0],ans[1]))
        except:
            break

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

isPrime = [True] * 60001
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,60000):
        if isPrime[i]:
            primes.append(i)
eratos(60000)

while True:
    try:
        p = int(input())
        min = list(filter(lambda x: x < p,primes))
        max = list(filter(lambda x: x > p,primes))
        print(min[-1],max[0])
    except:
        break

Submission status: Accepted

Solution code:
import math

def first_try(num):
    list=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67]
    i=0
    tmp=int(math.sqrt(num))
    while True:
        if num in list:
            return True
        #その数を超えたら終了
        if list[i]>tmp or i==len(list)-1:
            return True
        
        if (num%list[i]==0):
            return False
        i+=1

while True:
    try:
        num=int(input())
    except:
        break

    #小さいの
    s=0
    while True:
        s+=1
        if first_try(num-s)==True:
            print(num-s,end=" ")
            break
    #大きいの
    l=0
    while True:
        l+=1
        if first_try(num+l)==True:
            print(num+l)
            break

Submission status: Accepted

Solution code:
import bisect
L = [True] * 60000
L[0] = L[1] = False

for i in range(2,int(60000**0.5)+1):
    if not L[i]:
        continue
    for j in range(i*2,60000, i):
        L[j] = False
p = [x for x in range(60000) if L[x]]
#print(" ".join(map(str,p)))
while True:
    try:
        n = int(input())
    except EOFError:
        break
    k = bisect.bisect_left(p,n)
    a = p[k-1]

    if p[k] == n:
        b = p[k+1]
    else:
        b = p[k]
    print(a,b)

Submission status: Accepted

Solution code:
l = [2]
for i in range(3, 60000):
    flag = True
    for j in l:
        if i % j == 0:
            flag = False
            break
    if flag:
        l.append(i)

while True:
    try:
        n = int(input())
    except:
        break
    a = b = 0
    for k in range(1, n):
        if n -k in l:
            a = n-k
            break
    for kk in range(1, 10000):
        if n+kk in l:
            b=n+kk
            break
    print(a,b)

Submission status: Accepted

Solution code:
p = [1] * (100000 + 1)
p[0], p[1] = 0, 0
for i in range(2, int(100000 ** 0.5) + 1):
    if not p[i]:
        continue
    for j in range(2 * i, 100000 + 1, i):
        p[j] = 0

while 1:
    try:
        n = int(input())
        bp, ap = 0, 0
        for i in range(n)[::-1]:
            if p[i] == 1:
                bp = i
                break
        for i in range(n+1, 2 * n + 1):
            if p[i] == 1:
                ap = i
                break
        print(bp, ap)
    except:
        break

Submission status: Accepted

Solution code:
N = 50050
a = [True] *  N
i = 3
while i * i < N:
    for j in range(3 * i, N, 2 * i): a[j] = False
    i += 2
  
while True:
    try:
        n = int(input())
    except:
        break
 
    n0 = n + 2 if (n & 1) else n + 1
    for max in range(n0, N, 2):
        if a[max]: break
    n0 = n - 2 if (n & 1) else n - 1
    for min in range(n0, 2, -2):
        if a[min]: break
    else:
        min = 2
 
    print(min, max)

Submission status: Accepted

Solution code:
MAX = 50025
SQRT = 223     # sqrt(MAX)
 
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:
    try:
        n = int(input())
    except EOFError:
        break
         
    for i in range(n-1, 1, -1):
        if prime[i]:
            a = i
            break
    for i in range(n+1, MAX):
        if prime[i]:
            b = i
            break   
    print(a, b)

Submission status: Accepted

Solution code:
from math import sqrt

n = 50022
p = [1 for i in range(n)]
p[0] = 0
for i in range(1,int(sqrt(n))):
    if p[i]:
        for j in range(2*(i+1)-1,n,i+1):
            p[j] = 0

pmax = [0 for i in range(50022)]
pmin = [0 for i in range(50022)]
prev = 2

for i in range(50022):
    if p[i]:
        pmax[i] = i+1
        prev = i+1
    else:
        pmax[i] = prev
prev = 50021
for i in range(50001)[::-1]:
    if p[i]:
        pmin[i] = i+1
        prev = i+1
    else:
        pmin[i] = prev

while(1):
    try:
        n = int(input())
        print(pmax[n-2],pmin[n])
    except EOFError:
        break

Submission status: Accepted

Solution code:
import math

def is_prime(x):
    if x == 1: return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

while True:
    try: n = int(input())
    except: break
    
    low_prime = 0
    for i in range(n-1, 0, -1):
        if is_prime(i):
            low_prime = i
            break
    
    high_prime = n + 1
    while True:
        if is_prime(high_prime):
            break
        else:
            high_prime += 1

    print('{} {}'.format(low_prime, high_prime))

Submission status: Accepted

Solution code:
import sys

def isPrime(n):
    for i in range(2,int(n**.5+1)):
        if n%i==0:
            return False
    return True

for n in sys.stdin:
    n=int(n)
    s=n-1
    while not isPrime(s):
        s-=1
    b=n+1
    while not isPrime(b):
        b+=1
    print(*[s,b])

Submission status: Accepted

Solution code:
import sys

def check_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

for line in sys.stdin:
    ans = ''
    for i in range(int(line)-1, 1, -1):
        c = check_prime(i)
        if c == True:
            ans += str(i)
            break
    for i in range(int(line)+1, int(line)*2+1):
        c = check_prime(i)
        if c == True:
            ans += ' '
            ans += str(i)
            break
    print(ans)

Submission status: Runtime Error

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

def solve(n):
	i=0
	a,b=0,0
	while True:
		if n>prime[i]:
			a=prime[i]
		elif n==prime[i]:
			a=prime[i-1]
		else:
			b=prime[i]
			break
		i+=1
	print(a,b)

prime=sieve(5100)
while True:
	try:
		n=int(input())
		solve(n)
	except EOFError:
		break

Submission status: Runtime Error

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

def solve(n):
	i=0
	while True:
		if n>prime[i]:
			a=prime[i]
		elif n==prime[i]:
			a=prime[i-1]
		else:
			b=prime[i]
			break
		i+=1
	print(a,b)

prime=sieve(5003)
while True:
	try:
		n=int(input())
		solve(n)
	except EOFError:
		break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys

primes = [2]
for i in range(3, 50010):
    flag = True
    for p in primes:
        if i % p == 0:
            flag = False
            break
    if flag:
        primes.append(i)

for line in sys.stdin:
    n = int(line)
    i = 0
    while primes[i] < n and i < len(primes):
        i += 1
    if primes[i] == n:
        s = primes[i-1]
    else:
        s = primes[i]
    m = primes[i+1]
    print s, m

Submission status: Runtime Error

Solution code:
import sys
from itertools import takewhile, dropwhile

L, pn, tmp = 224, [], [i for i in range(2, 50000)]
while tmp[0] < 224:
    v = tmp.pop(0)
    pn.append(v)
    tmp = list(filter(lambda x: x%v!=0, tmp))
for t in tmp: pn.append(t)

for line in sys.stdin:
    n = int(line.strip())
    print(list(takewhile(lambda x: x<n, pn))[-1], list(dropwhile(lambda x: x<n, pn))[1])

Submission status: Runtime Error

Solution code:
from itertools import takewhile, dropwhile
pn, tmp = [], [i for i in range(2, 50000)]
while tmp[0] < 224:
    v = tmp.pop(0)
    pn.append(v)
    tmp = list(filter(lambda x: x%v!=0, tmp))
for t in tmp: pn.append(t)
while True:
    try:
        n = int(input())
    except:
        break
    print(list(takewhile(lambda x: x<n, pn))[-1], list(dropwhile(lambda x: x<=n, pn))[0])

Submission status: Runtime Error

Solution code:
from itertools import takewhile, dropwhile
pn, tmp = [], [i for i in range(2, 50000)]
while tmp[0] < 224:
    v = tmp.pop(0)
    pn.append(v)
    tmp = list(filter(lambda x: x%v!=0, tmp))
for t in tmp: pn.append(t)
while True:
    try:
        n = int(input())
    a, b = list(takewhile(lambda x: x<n, pn))[-1], list(dropwhile(lambda x: x<=n, pn))[0]
    print(a, b)
    except:
        break

Submission status: Runtime Error

Solution code:
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
p=[i for i in range(n+1) if p[i]==1]
while 1:
    try:n=int(input())
    except:break
    i=p.index(n)
    print(p[i-1],p[i+1])

Submission status: Runtime Error

Solution code:
primes = [0, 0] + [1]*49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
while True:
    try:
        n = int(input())
    except:
        break
    m, o = n-1, n+1
    while not primes[m]:
        m -= 1
    while not primes[o]:
        o += 1
    print(m, o)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044
?´???°II
"""
import sys


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 = []
    # print('x={0}'.format(x))
    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)
    # print(primes)
    return primes


def main(args):
    primes = create_prime_list(50000)  # ?´???°????????????????????¨???
    
    for line in sys.stdin:  # ??????????????\???
        limit = int(line.strip())
        unders = [x for x in primes if x < limit]
        largest_prime = unders[-1]
        overs = [x for x in primes if x > limit]
        smallest_prime = overs[0]
        
        # ???????????????
        print('{0} {1}'.format(largest_prime, smallest_prime))


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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math
import itertools

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

for s in sys.stdin:
    n = int(s)

    for i in range(n-1, 3, -1):
        if is_prime(i):
            answer0 = i
            break

    for i in range(n+1, 50000):
        if is_prime(i):
            answer1 = i
            break

    print(answer0, answer1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math
import itertools

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

for s in sys.stdin:
    n = int(s)

    for i in range(n-1, 3, -1):
        if is_prime(i):
            answer0 = i
            break

    for i in range(n+1, 100000, 1):
        if is_prime(i):
            answer1 = i
            break

    print(answer0, answer1)

Submission status: Runtime Error

Solution code:
#include <stdio.h>
int pm(int n,int *l){
    int i,j,p=0,c=n-1,target[n-1];
    for(i=0;i<n-1;i++){target[i]=i+2;}
    for(i=0;i<n-1;i++){
        if (!target[i]){continue;}
        for(j=i;j<n-1;j=j+i+2){
            if (!target[j]){continue;}
            if (j!=i && target[j]%target[i]==0){target[j]=0;c--;}
        }
    }
    for(i=0;i<n-1;i++){
        if(target[i]){l[p]=target[i];p++;}
    } 
    return p;
} 

int main(void){
    int i,p,n,idx=0,l[59999],ds[50000][2];
    p=pm(60000,l);

    while(scanf("%d",&n)!=EOF){
        for(i=0;i<p-1;i++){
            if(n>l[i]&&n<l[i+1]){
                if((n-l[i]) > (l[i+1]-n)){ds[idx][0]=l[i];ds[idx][1]=l[i+2];break;}
                if((n-l[i]) < (l[i+1]-n)){ds[idx][0]=l[i-1];ds[idx][1]=l[i+1];break;}
	    }
            else if(n==l[i]){ds[idx][0]=l[i-1];ds[idx][1]=l[i+1];break;}
            else if(n==l[i+1]){ds[idx][0]=l[i];ds[idx][1]=l[i+2];break;}
        }
        idx++;
    }
    for(i=0;i<idx;i++){printf("%d %d\n",ds[i][0],ds[i][1]);}
    return 0;
}

Submission status: Runtime Error

Solution code:
q=[]
for i in range(2,10000):
  for j in range(2,i):
    if i % j == 0:
      break
  else:
    q.append(i)

if __name__ =='__main__':
  while True:
    try:
      a = int(input())
      ans = q.index(a)
      print q[ans-1],q[ans+1]
    except EOFError: break

Submission status: Runtime Error

Solution code:
import sys
def is_prime(q):
&#160;&#160;&#160;&#160;q = abs(q)
&#160;&#160;&#160;&#160;if q == 2: return True
&#160;&#160;&#160;&#160;if q < 2 or q&1 == 0: return False
&#160;&#160;&#160;&#160;return pow(2, q-1, q) == 1
for n in sys.stdin:
&#160;&#160;&#160;&#160;a=int(n.strip())
&#160;&#160;&#160;&#160;b=a
&#160;&#160;&#160;&#160;while 1:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;a+=2
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;if is_prime(a):
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;max_a=a
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;break
&#160;&#160;&#160;&#160;while 1:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;b-=2
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;if is_prime(b):
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;min_b=b
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;break
&#160;&#160;&#160;&#160;print min_b,max_a

Submission status: Runtime Error

Solution code:
from sys import stdin
te=lambda x:pow(2,x-1,x) == 1
for i in stdin:
    a=b=int(i.strip())
    while 1:
        a+=1
        if te(a):
            ans=a
            break
    while 1:
        b-=1
        if te(b):
            ans2=b
            break
    print ans,ans2

Submission status: Runtime Error

Solution code:

import sys


primes = [2]

def solv(num):
    if num < primes[-1]:
        p1 = filter(lambda x: x < num)[-1]
    else:
        for p in prime_list(num * 2):
            primes.append(p)
            if num < p:
                p2 = p
                break
            else:
                if p < num:
                    p1 = p
    return (p1, p2)


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]



for line in sys.stdin:
    number = int(line)
    p1, p2 = solv(number)
    print ' '.join(map(str, [p1, p2]))

Submission status: Runtime Error

Solution code:

import sys


primes = [2]

def solv(num):
    if num < primes[-1]:
        p1 = filter(lambda x: x < num, primes)[-1]
    else:
        for p in prime_list(num * 2):
            primes.append(p)
            if num < p:
                p2 = p
                break
            else:
                if p < num:
                    p1 = p
    return (p1, p2)


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]



for line in sys.stdin:
    number = int(line)
    p1, p2 = solv(number)
    print ' '.join(map(str, [p1, p2]))

Submission status: Runtime Error

Solution code:
M = 50100
p = [1]*M; p[0],p[1]=0,0;
pm = [0]*M; pM = [0]*M;
for i in range(2,M):
    if p[i]:
        for j in range(i*i,M,i): p[j] = 0
num = -1
for i in range(1,M):
    pm[i] = num
    if p[i]: num = i
num = -1
for i in range(M-1,2,-1):
    pM[i] = num
    if p[i]: num = i
while 1:
    n = input()
    if n==0: break
    print pm[n],pM[n]

Submission status: Runtime Error

Solution code:
import math
&#160;
r = 50000
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
&#160;&#160;&#160;&#160;if p[i]:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;for j in range(2*i+1,r,i+1):
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;p[j] = 0
&#160;
while True:
&#160;&#160;&#160;&#160;try:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;n = int(raw_input())
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;for i in range(n,50000):
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;    if p[i] == 1:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;        lp = i
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;        break
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;for i in range(n-1,3,-1):
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;    if p[i] == 1:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;        sp = i
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;        break
&#160;&#160;&#160;&#160;&#160;&#160;&#160; print lp, sp
&#160;&#160;&#160;&#160;except:
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;break

Submission status: Runtime Error

Solution code:
import sys 
def sieves(m):
    global S
    S = range(1,m+1,2)
    r = int(m**.5)
    h = len(S)
    S[0] = 0
    for i in range(h):
        x = S[i]
        if x>r: break
        if x and i+x<h: S[i+x:h:x] = [0]*((h-1-i-x)/x+1)
    S[0] = 2
    return

S=[]
sieves(50001)
for s in sys.stdin:
    n = int(s)
    p1 = n/2-1
    p2 = (n+1)/2
    while S[p1]==0: p1 -=1
    while S[p2]==0: p2 +=1
    print S[p1],S[p2]

Submission status: Runtime Error

Solution code:
import sys
m = 50001
S = range(1,m+1,2)
r = int(m**.5)
h = len(S)
S[0] = 0
for i in range(h):
    x = S[i]
    if x>r: break
    if x and i+x<h: S[i+x:h:x] = [0]*((h-1-i-x)/x+1)
S[0] = 2

for s in sys.stdin:
    n = int(s)
    for p1 in range(n/2-1,0,-1):
        if S[p1]: break
    for p2 in range((n+1)/2,m/2):
        if S[p2]: break
    print S[p1],S[p2]

Submission status: Runtime Error

Solution code:
import sys,math
def sieves(m):
    global S
    S = range(1,m+1,2)
    r = int(m**.5)
    h = len(S)
    S[0] = 0
    for i in range(h):
        x = S[i]
        if x>r: break
        if x and i+x<h: S[i+x:h:x] = [0]*((h-1-i-x)/x+1)
    S[0] = 2
    return
m = 50100
sieves(m)
for s in sys.stdin:
    n = int(s)
    for p1 in range(n/2-1,0,-1):
        if S[p1]: break
    for p2 in range((n+1)/2,m/2+1):
        if S[p2]: break
    print S[p1],S[p2]

Submission status: Runtime Error

Solution code:
import sys,math
def sieves(m):
    global S
    S = range(1,m+1,2)
    r = int(m**.5)
    h = len(S)
    S[0] = 0
    for i in range(h):
        x = S[i]
        if x>r: break
        if x and i+x<h: S[i+x:h:x] = [0]*((h-1-i-x)/x+1)
    S[0] = 2
    return
m = 50100
S = []
sieves(m)
for s in sys.stdin:
    n = int(s)
    for p1 in range(n/2-1,0,-1):
        if S[p1]: break
    for p2 in range((n+1)/2,m/2+1):
        if S[p2]: break
    print S[p1],S[p2]

Submission status: Runtime Error

Solution code:
from bisect import *

def sieve(n):
    a = range(n)
    a[:2] = None, None
    for i in range(2, n):
        if i ** 2 >= n: break
        if not a[i]: continue
        for i in range(i ** 2, n, i):
            a[i] = None
    return [v for v in a if v]

try:
    a = sieve(9000)
    while True:
        n = int(raw_input())
        i = bisect_right(a, n)
        print a[i - (2 if a[i - 1] == n else 1)], a[i]
except EOFError:
    pass

Submission status: Runtime Error

Solution code:
N = 50001
a = [True] *  N
i = 3
while i * i < N:
    for j in range(3 * i, N, 2 * i): a[j] = False
    i += 2
 
while True:
    try:
        n = int(input())
    except:
        break

    n0 = n + 2 if (n & 1) else n + 1
    for maxv in range(n0, N, 2):
        if a[maxv]: break
    n0 = n - 2 if (n & 1) else n - 1
    for minv in range(n0, 2, -2):
        if a[minv]: break

    print(minv, maxv)

Submission status: WA: Presentation 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

while(True):
    try:
        a = int(raw_input())
    except:
        break
    b = a
    
    while(True):
        b -= 1
        if(is_prime(b)):
            print b , " ",
            break

    while(True):
        a+=1
        if(is_prime(a)):
            print a
            break