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: Wrong Answer

Solution code:
import math
def p_l(n):
    for i in range(n-1, 2, -1):
        flag=0
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                flag=1
        if flag==1:continue
        return i
def p_h(n):
    for i in range(n+1,50022):
        flag=0
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                flag=1
        if flag==1:continue
        return i   
while 1:
    try:
        n=int(input())
        print(p_l(n),p_h(n))
    except:break

Submission status: Wrong Answer

Solution code:
def sieve(n):
    res = []
    nums = [1] * n
    nums[0] = 0
    for i in range(int(n ** 0.5) + 1):
        if nums[i] == 0: continue
        j = 2
        while (i + 1) * j <= n:
            nums[(i+1) * j - 1] = 0
            j += 1
    for i in range(len(nums)):
        if nums[i] == 1:
            res.append(i+1)
    return res

primes = sieve(50000)

while True:
    try:
        n = int(input())
        minn, maxn = 0, 0
        for i in range(len(primes)):
            if primes[i] > n:
                maxn = primes[i]
                minn = primes[i-1]
                if minn == n: minn = primes[i-2]
                break
        print('%d %d' % (minn, maxn))
    except:
        break

Submission status: Wrong Answer

Solution code:
from sys import *

maxnum = 60000
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in xrange(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in xrange(i*2,maxnum,i): primes[j] = False

for s in stdin:
    d = int(s)
    for i in reversed(xrange(2,d-1)):
        if primes[i]: print i,; break
    for i in xrange(d+1,maxnum):
        if primes[i]: print i;break

Submission status: Wrong Answer

Solution code:
import sys
n=60000
prime = [1]*(n+1)
(prime[0],prime[1])=(0,0)
for i in [v for v in xrange(2,n+1) if v*v<n+1]:
        for j in xrange(i*i,n+1,i):
            prime[j]=0
 
for inp in ["19","3517"]:
    i=int(inp)
    j=int(inp)
    while i<n:
        if prime[i+1]==1:
            break
        i+=1

    while j>0:
        if prime[j-1]==1:
            break
        j-=1
    print j-1,i+1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import bisect
import sys
def sieve(n):
    prime = []
    isprime = [1] * n
    isprime[0] = isprime[1] = False
    for i in range(2, n):
        if(isprime[i] == False):continue
        prime.append(i)
        for j in range(2*i, n, i):
            isprime[j] = False
    return prime

prime = sieve(100000)    
for n in sys.stdin:
    n = int(n)
    m = bisect.bisect_left(prime, n)
    print prime[m - 1], prime[m + 1]

Submission status: Wrong Answer

Solution code:
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
l=[]
for i in range(2,50000):
    if prime_t(i):
        l.append(i)
#print l
while 1:
    try:
        o=y=50000
        n=int(raw_input())
        for i in l:
            if y<n and n<i:
                print y,i
                break
            elif y==n and o<n and n<i:
                print o,i
                break
            o=y
            y=i
        
    except:
        break

Submission status: Wrong Answer

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

import sys

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

for line in sys.stdin:
    n = int(line)
    if n == 50000:
        print "49999 50021"
    else:
        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: Wrong Answer

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

import sys

primes = [2]
for i in range(3, 50022):
    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)
    if n == 50000:
        print "49999 50021"
    else:
        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: Wrong Answer

Solution code:
pr=[True]*50001
for i in range(2,224):
    if pr[i]:
        for j in range(i*2,50001,i):
            pr[j]=False

while True:
    try:
        n=int(input())
    except:
        break
    for i in range(n-1,0,-1):
        if pr[i]:
            print(i,end=" ")
            break
    for i in range(n+1,50001):
        if pr[i]:
            print(i)
            break

Submission status: Wrong Answer

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())
        print(list(takewhile(lambda x: x<n, pn))[-1], list(dropwhile(lambda x: x<=n, pn))[0])
    except:
        break

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
def f(s,p):
    p.append(s.pop(0))
    for i,num in enumerate(s):
        if num % p[-1] == 0:
            s.pop(i)
    return 0

def vol44(k):
    for i in range(len(p)):
        if p[i] == k:
            print(p[i-1],p[i+1])
            break
        elif p[i] > k:
            print(p[i-1],p[i])
            break

primes = list(range(2,50000))
arr = []
while not arr or arr[-1] ** 2 < primes[-1]:
    f(primes,arr)
p = arr+primes

n = []
while True:
    try:
        n.append(int(input()))
    except EOFError:
        break

for i in range(len(n)):
    vol44(n[i])

Submission status: Wrong Answer

Solution code:
# Aizu Problem 0009: Prime Number
#
import sys, math, os, bisect

# read input:
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(50000)

for line in sys.stdin:
    n = int(line)
    if n in primes:
        idx = primes.index(n)
        print(primes[idx-1], primes[idx+1])
    #idx = bisect.bisect_right(primes, n)
    #print(idx)

Submission status: Wrong Answer

Solution code:
import sys
import math

primes = [2]
for line in sys.stdin:
  n = int(line)
  for i in range(max(primes) + 1, n):
    if i % 2 == 0:
      continue
    elif math.sqrt(i) == 0:
      continue
    elif len([j for j in primes if i % j == 0]) > 0:
      continue
    primes.append(i)
  for i in range(n - 1, 1, -1):
    if i % 2 == 0:
      continue
    elif math.sqrt(i) == 0:
      continue
    elif len([j for j in primes if i % j == 0 and i != j]) > 0:
      continue
    print(i, end=" ")
    break
  for i in range(n + 1, n + 1000):
    if i % 2 == 0:
      continue
    elif math.sqrt(i) == 0:
      continue
    elif len([j for j in primes if i % j == 0]) > 0:
      continue
    print(i)
    break

Submission status: Wrong Answer

Solution code:
import sys
import math

primes = [2]
for line in sys.stdin:
  n = int(line)
  for i in range(max(primes) + 1, n):
    if i % 2 == 0:
      continue
    elif math.sqrt(i) == 0:
      continue
    elif len([j for j in primes if i % j == 0]) > 0:
      continue
    primes.append(i)
  for i in range(n - 1, 1, -1):
    if i % 2 == 0:
      continue
    elif math.sqrt(i) == 0:
      continue
    elif len([j for j in primes if i % j == 0 and i != j]) > 0:
      continue
    print(i, end=" ")
    break
  for i in range(n + 1, n + 1000):
    if i % 2 == 0:
      continue
    elif math.sqrt(i) == 0:
      continue
    elif len([j for j in primes if i % j == 0 and i != j]) > 0:
      continue
    print(i)
    break

Submission status: Wrong Answer

Solution code:
import sys
import math

primes = [2]
for line in sys.stdin:
  try:
    n = int(line)
    for i in range(max(primes) + 1, n):
      if i % 2 == 0:
        continue
      elif math.sqrt(i) == 0:
        continue
      elif len([j for j in primes if i % j == 0]) > 0:
        continue
      primes.append(i)
    for i in range(n - 1, 1, -1):
      if i % 2 == 0:
        continue
      elif math.sqrt(i) == 0:
        continue
      elif len([j for j in primes if i % j == 0 and i != j]) > 0:
        continue
      print(i, end=" ")
      break
    for i in range(n + 1, n + 1000):
      if i % 2 == 0:
        continue
      elif math.sqrt(i) == 0:
        continue
      elif len([j for j in primes if i % j == 0 and i != j]) > 0:
        continue
      print(i)
      break
  except:
    break

Submission status: Wrong Answer

Solution code:
import sys
import math

primes = [2]
for line in sys.stdin:
  try:
    n = int(line)
    for i in range(max(primes) + 1, n):
      if i % 2 == 0:
        continue
      elif math.sqrt(i) == 0:
        continue
      elif len([j for j in primes if i % j == 0]) > 0:
        continue
      primes.append(i)
    for i in range(n - 1, 1, -1):
      if i % 2 == 0:
        continue
      elif math.sqrt(i) == 0:
        continue
      elif len([j for j in primes if i % j == 0 and i != j]) > 0:
        continue
      print(i, end=" ")
      break
    for i in range(n + 1, n + 10000):
      if i % 2 == 0:
        continue
      elif math.sqrt(i) == 0:
        continue
      elif len([j for j in primes if i % j == 0 and i != j]) > 0:
        continue
      print(i)
      break
  except:
    break

Submission status: Wrong Answer

Solution code:
import sys
import math

primes = [2]
for line in sys.stdin:
  try:
    n = int(line)
    for i in range(max(primes) + 1, n):
      if i % 2 == 0:
        continue
      elif math.sqrt(i) == 0:
        continue
      elif len([j for j in primes if i % j == 0]) > 0:
        continue
      primes.append(i)
    print(primes[-1] if primes[-1] != n else primes[-2], end=" ")
    for i in range(n + 1, n + 10000):
      if i % 2 == 0:
        continue
      elif math.sqrt(i) == 0:
        continue
      elif len([j for j in primes if i % j == 0 and i != j]) > 0:
        continue
      print(i)
      break
  except:
    break

Submission status: Wrong Answer

Solution code:
# 04.77 sec -> Time Limit Exceeded?
import sys
import math

# Sieve of Eratosthenes
N = 50000
searchList = list(range(3, N + 1, 2))
primes = [2]
while True:
  top = searchList.pop(0)
  primes.append(top)
  if top > math.sqrt(N):
    break
  searchList = [s for s in searchList if s % top != 0]
primes.extend(searchList)


for line in sys.stdin:
  try:
    n = int(line)
    pre = 2
    for p in primes:
      if p < n:
        pre = p
      if p > n:
        print(pre, p)
        break
  except:
    break

Submission status: Wrong Answer

Solution code:
def main():
    while True:
        try:
            value = int(input())
            prime_MAX = 0
            for v in range(2,value-1):
                flag = 0
                for _v in range(2,int(v**0.5)):
                    if v%_v == 0:
                        flag = 777
                        break
                if flag == 0:
                    prime_MAX = v 

            for v in range(value+1,50000):
                flag = 0
                for _v in range(2,int(v**0.5)):
                    if v%_v == 0:
                        flag = 777
                        break
                if flag == 0:
                    print(str(prime_MAX)+" "+str(v))
                    break
                
        except EOFError:
            break

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    while True:
        try:
            value = int(input())
            prime_MAX = 0
            for v in range(2,value-1):
                if is_prime(v):
                    prime_MAX = v
            for v in range(value+1,50000):
                if is_prime(v):
                    break
            print(str(prime_MAX)+" "+str(v))        
        except EOFError:
            break

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    while True:
        try:
            value = int(input())
            prime_MAX = 0
            for v in range(2,value):
                if is_prime(v):
                    prime_MAX = v
            for v in range(value+1,50001):
                if is_prime(v):
                    break
            print(str(prime_MAX)+" "+str(v))        
        except EOFError:
            break

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    while True:
        try:
            value = int(input())
            for v in range(0,value):
                if is_prime(v):
                    prime_MAX = v
            for v in range(value+1,10000):
                if is_prime(v):
                    break
            print(str(prime_MAX)+" "+str(v))        
        except EOFError:
            break

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import os
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

def main():
    for Value in sys.stdin:
        value = int(Value)
        for v in range(0,value):
            if is_prime(v):
                prime_MAX = v
        for v in range(value+1,10000):
            if is_prime(v):
                break
        print(str(prime_MAX)+" "+str(v))        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import os
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

def main():
    for Value in sys.stdin:
        value = int(Value)
        for v in range(0,value):
            if is_prime(v):
                prime_MAX = v
        for v in range(value+1,10000):
            if is_prime(v):
                break
        print(prime_MAX,v)        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = 50000
c = [1 for i in range(n)]
c[0] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j <= n:
        c[j - 1] = 0
        j += i
    i += 1

while True:
    try:
        n = int(input())
        i, a, b = 0, 0, 0
        while a == 0 and b == 0:
            i += 1
            if n - i >= 0 and a == 0 and c[n - i] == 1:
                a = n - i
            if n + i < 50000 and b == 0 and c[n + i] == 1:
                b = n + i
        print(a,b)
    except:
        break

Submission status: Wrong Answer

Solution code:
n = 50000
c = [1 for i in range(n)]
c[0] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j <= n:
        c[j - 1] = 0
        j += i
    i += 1

c2 = []
for i in range(50000):
    if c[i] == 1:
        c2.append(i + 1)

while True:
    try:
        n = int(input())
        n_ind = c2.index(n)
        print(c2[n_ind - 1], c2[n_ind + 1])
    except:
        break

Submission status: Wrong Answer

Solution code:
a = [0, 0, 1, 1] + [0, 1] * 24999
for i in range(3, 50001, 2):
    if a[i]:
        for j in range(2, 50001 // i):a[i * j] = 0
while 1:
    try:
        n = int(input())
        print("{} {}".format(n - 1 - a[:n][::-1].index(1), n + 1 + a[n + 1:].index(1)))
    except:break

Submission status: Wrong Answer

Solution code:
import bisect

MAX = 60000

#エラトステネスの篩
is_prime = [True for _ in range(MAX)]
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX ** (1 / 2)) + 1):
  if is_prime[i]:
    for j in range(i ** 2, MAX, i):
      is_prime[j] = False

primes = [i for i in range(MAX) if is_prime[i]]

while True:
  try:
    n = int(input())
    ind = bisect.bisect_left(primes, n)
    if primes[ind] == n:
      print(primes[ind - 1], primes[ind + 1])
    else:
      print(primes[ind], primes[ind + 1])

  except EOFError:
    break

Submission status: Wrong Answer

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())
      if a in q:
        ans = q.index(a)
        print q[ans-1],q[ans+1]
      else:
        for i in range(100):
          if a-i in q:
            ans = q.index(a-i)
            print q[ans-1],q[ans+1]
            break
          elif a+i in q:
            print q[ans-1],q[ans+1]
            break
    except EOFError: break

Submission status: Wrong Answer

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
n=input()
a,b=n,n
while 1:
    a+=1
    if is_prime(a):
        max_a=a
        break
while 1:
    b-=1
    if is_prime(b):
        min_b=b
        break
print min_b,max_a

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def prime(n):
    L = list(xrange(2, n))
    P = []
    while L[0] ** 2 < n:
        P.append(L[0])
        L = [i for i in L if i % P[-1]]
    return P + L

ps = prime(50030)
for line in stdin:
    n = int(line)
    for p in ps:
        if n < p:
            upper = p
            break
        under = p
    print(under, upper)

Submission status: Wrong Answer

Solution code:
import sys

p = [True] * (50001)
p[0] = p[1] = False
for i in range(2, 50001):
    if p[i]:
        for j in range(i * 2, 50001, i):
            p[j] = False

for s in sys.stdin.read().rstrip().split('\n'):
    n = int(s)
    for i in range(n-1, 0, -1):
        if p[i]:
            m1 = i
            break
    for i in range(n+1, len(p)):
        if p[i]:
            m2 = i
            break
    print m1, m2

Submission status: Wrong Answer

Solution code:
import math

def get_primes(max_number):
    if max_number == 2:
        return [2]
    elif max_number < 3:
        return []
     
    numbers = range(1, max_number + 2, 2)
    nroot = math.floor(max_number ** 0.5)
    n = len(numbers)
    numbers[0] = 0
    for i in range(1, n):
        x = numbers[i]
        if x > nroot:
            break
        if x and i + x < n:
            for j in range(i+x, n, x):
                numbers[j] = 0
    x=[2] + filter(None, numbers[1:])
    return x

primes = get_primes(50000)
while True:
    try:
        n = input()
    except:
        break
    for a in primes:
        if a<n: b=a
        elif a>n: break
    print b,a

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

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
    else:
        minv = 2

    print(minv, maxv)

Submission status: Wrong Answer

Solution code:
N = 50010
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
    else:
        minv = 2

    print(minv, maxv)

Submission status: Time Limit Exceeded

Solution code:
import sys

def primegen():
  l = [2]
  while True:
    yield max(l)
    n = max(l)
    while True:
      n += 1
      flag = 1
      for i in l:
        if n % i == 0:
          flag = 0
          break
      if flag:
        l.append(n)
        break

for line in sys.stdin:
  n = int(line)
  seq = primegen()
  i1 = 0
  i2 = 0
  while i2 < n:
    i1 = i2
    i2 = seq.__next__()
  if i2 == n:
    i2 = seq.__next__()
  print(str(i1) + " " + str(i2))

Submission status: Time Limit Exceeded

Solution code:
def main():
    while True:
        try:
            value = int(input())
            prime_MAX = 0
            for v in range(2,value-1):
                flag = 0
                for _v in range(2,v):
                    if v%_v == 0:
                        flag = 777
                        break
                if flag == 0:
                    prime_MAX = v 

            for v in range(value+1,50000):
                flag = 0
                for _v in range(2,v):
                    if v%_v == 0:
                        flag = 777
                        break
                if flag == 0:
                    print(str(prime_MAX)+" "+str(v))
                    break
                
        except EOFError:
            break

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = 50000
c = [1 for i in range(n)]
c[0] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j <= n:
        c[j - 1] = 0
        j += i
    i += 1

while True:
    try:
        n = int(input())
        i, a, b = 0, 0, 0
        while a == 0 or b == 0:
            i += 1
            if n - i - 1 >= 0 and a == 0 and c[n - i - 1] == 1:
                a = n - i
            if n + i - 1 < 50000 and b == 0 and c[n + i - 1] == 1:
                b = n + i
        print(a,b)
    except:
        break

Submission status: Time Limit Exceeded

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
for n in sys.stdin:
    a=int(n.strip())
    b=a
    while 1:
        a+=2
        if is_prime(a):
            max_a=a
            break
    while 1:
        b-=2
        if is_prime(b):
            min_b=b
            break
    print min_b,max_a

Submission status: Accepted

Solution code:
from math import sqrt, ceil

N = 53000
temp = [True]*(N+1)
temp[0] = temp[1] = False
for i in range(2, ceil(sqrt(N+1))):
    if temp[i]:
        temp[i+i::i] = [False]*(len(temp[i+i::i]))

while True:
    try:
        n = int(input())
        print(n-1-temp[n-1:0:-1].index(True), n+1+temp[n+1:].index(True))
    except EOFError: break

Submission status: Accepted

Solution code:
import math
def p_l(n):
    for i in range(n-1, 1, -1):
        flag=0
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                flag=1
        if flag==1:continue
        return i
def p_h(n):
    for i in range(n+1,50022):
        flag=0
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                flag=1
        if flag==1:continue
        return i   
while 1:
    try:
        n=int(input())
        print(p_l(n),p_h(n))
    except:break

Submission status: Accepted

Solution code:
def sieve(n):
    res = []
    nums = [1] * n
    nums[0] = 0
    for i in range(int(n ** 0.5) + 1):
        if nums[i] == 0: continue
        j = 2
        while (i + 1) * j <= n:
            nums[(i+1) * j - 1] = 0
            j += 1
    for i in range(len(nums)):
        if nums[i] == 1:
            res.append(i+1)
    return res

primes = sieve(50021)

while True:
    try:
        n = int(input())
        minn, maxn = 0, 0
        for i in range(len(primes)):
            if primes[i] > n:
                maxn = primes[i]
                minn = primes[i-1]
                if minn == n: minn = primes[i-2]
                break
        print('%d %d' % (minn, maxn))
    except:
        break

Submission status: Accepted

Solution code:
isPrime = [True] * 50100
prime = []
def calcPrime():
    isPrime[0] = isPrime[1] = False
    for i in range(len(isPrime)):
        if(isPrime[i]):
            prime.append(i)
            for j in range(2 * i, len(isPrime), i):
                isPrime[j] = False

calcPrime()
while(True):
    try:
        n = input()
        pos = 0
        while(prime[pos] < n):
            pos += 1
        print(prime[pos - 1]),
        if(n == prime[pos]):
            print(prime[pos + 1])
        else:
            print(prime[pos])
    except Exception:
        break

Submission status: Accepted

Solution code:
from sys import *

maxnum = 60000
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in xrange(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in xrange(i*2,maxnum,i): primes[j] = False

for s in stdin:
    d = int(s)
    for i in reversed(xrange(2,d)):
        if primes[i]: print i,; break
    for i in xrange(d+1,maxnum):
        if primes[i]: print i;break

Submission status: Accepted

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

def under(prime, n):
    for i in range(n - 1, -1, -1):
        if prime[i]:
            return i
def over(prime, n):
    for i in range(n + 1, len(prime)):
        if prime[i]:
            return i
import sys
n = [int(line) for line in sys.stdin]

prime = create_prime(max(n) + 100)

for ni in n:
    print(under(prime, ni), over(prime, ni))

Submission status: Accepted

Solution code:
def is_prime(n): 
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True
  

while True:
    try:
        n = int(raw_input())
    except EOFError:
        break    
    k = n - 1
    m = n + 1
    while not is_prime(k):
        k -= 1
    while not is_prime(m):
        m += 1
    print k,m

Submission status: Accepted

Solution code:
import sys
n=60000
prime = [1]*(n+1)
(prime[0],prime[1])=(0,0)
for i in [v for v in xrange(2,n+1) if v*v<n+1]:
        for j in xrange(i*i,n+1,i):
            prime[j]=0
 
for inp in sys.stdin:
    i=int(inp)
    j=int(inp)
    while i<n:
        if prime[i+1]==1:
            break
        i+=1

    while j>0:
        if prime[j-1]==1:
            break
        j-=1
    print j-1,i+1

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import bisect
import sys
def sieve(n):
    prime = []
    isprime = [1] * n
    isprime[0] = isprime[1] = False
    for i in range(2, n):
        if(isprime[i] == False):continue
        prime.append(i)
        for j in range(2*i, n, i):
            isprime[j] = False
    return prime

prime = sieve(100000)
for n in sys.stdin:
    n = int(n)
    m = bisect.bisect_left(prime, n)
    if n == prime[m]:
        print prime[m - 1], prime[m + 1]
    else:
        print prime[m - 1], prime[m]

Submission status: Accepted

Solution code:
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
l=[]
for i in range(2,50022):
    if prime_t(i):
        l.append(i)
#print l
while 1:
    try:
        o=y=50000
        n=int(raw_input())
        for i in l:
            if y<n and n<i:
                print y,i
                break
            elif y==n and o<n and n<i:
                print o,i
                break
            o=y
            y=i
        
    except:
        break

Submission status: Accepted

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(50021)
while True:
	try:
		n=int(input())
		solve(n)
	except EOFError:
		break

Submission status: Accepted

Solution code:
import sys

def inp():
    for line in sys.stdin:
        i = 1
        while True:
            if is_prime(int(line[:-1]) - i) == True:
                print (int(line[:-1]) - i),
                break
            else:
                i += 1
        i = 1
        while True:
            if is_prime(int(line[:-1]) + i) == True:
                print (int(line[:-1]) + i)
                break
            else:
                i += 1

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__":
    inp()