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:
# -*- 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)
    i = 0
    while primes[i] < n and i < len(primes):
        i += 1
    if primes[i] == n:
        s = primes[i-1]
        m = primes[i+1]
    else:
        s = primes[i-1]
        m = primes[i]
    print s, m

Submission status: Accepted

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)
    i = 0
    while primes[i] < n and i < len(primes):
        i += 1
    if primes[i] == n:
        s = primes[i-1]
        m = primes[i+1]
    else:
        s = primes[i-1]
        m = primes[i]
    print s, m

Submission status: Accepted

Solution code:
def make_ps(n):
    nums = [True for i in range(n)]
    nums[0] = nums[1] = False
    p = 2
    sqrt = n ** 0.5
    while p < sqrt:
        for i in range(2 * p, n, p):
            nums[i] = False
        while True:
            p += 1
            if nums[p]:
                break
    return [i for i in range(n) if nums[i]]
ps = make_ps(250)
def is_p(x):
    i = 0
    s = x ** 0.5
    while True:
        if ps[i] > s:
            break
        if not x % ps[i]:
            return False
        i += 1
    return True
while True:
    try:
        n = int(input())
    except:
        break
    for i in range(n - 1, 0, -1):
        if is_p(i):
            print(i, end=' ')
            break
    for i in range(n + 1, 50100):
        if is_p(i):
            print(i)
            break

Submission status: Accepted

Solution code:
import sys

def furui(n):
  l = [1 for i in range(n+1)]
  l[0] = 0
  l[1] = 0
  for i in range(2,n+1):
    if l[i] == 1:
      for j in range(2,n//i+1):
        l[i*j] = 0
  l2 = []
  for i in range (len(l)):
    if l[i] == 1:
      l2.append(i)
  return l2

for line in sys.stdin:
  n = int(line)
  l = furui(n)
  if max(l) == n:
    i1 = l[len(l)-2]
  else:
    i1 = max(l)
  i2 = n
  while True:
    i2 += 1
    flag = 1
    for i in l:
      if i2 % i == 0:
        flag = 0
        break
    if flag:
      break
  print(str(i1) + " " + str(i2))

Submission status: Accepted

Solution code:
pr=[True]*50100
for i in range(2,225):
    if pr[i]:
        for j in range(i*2,50100,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,50100):
        if pr[i]:
            print(i)
            break

Submission status: Accepted

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
    for i in range(len(p)):
        if p[i]==n:
            print(p[i-1],p[i+1])
            break 
        elif p[i]>n:
            print(p[i-1],p[i])
            break

Submission status: Accepted

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,50100))
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: Accepted

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

while True:
    try:
        N = int(input())
    except EOFError:
        break
    mx = 0
    mn = 0
    for i in range(N - 1,1,-1):
        if is_prime(i):
            mx = i
            break
    for i in range(N + 1,N * 2):
        if is_prime(i):
            mn = i
            break
    print(mx,mn)

Submission status: Accepted

Solution code:
primes = [0, 0] + [1]*50020
for i in range(2, 225):
    if primes[i]:
        for j in range(i*i, 50022, 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: Accepted

Solution code:
import bisect
prime = [2,3,5,7,11,13]

shieve1 = [1]*257
for i in prime:
    itr = i-1
    while(itr<256):
        shieve1[itr] = 0
        itr += i

for i in range(16,256):
    if shieve1[i]:
        prime.append(i+1)

shieve2 = [1]*(50101)

for i in prime:
    itr = i-1
    while(itr<50100):
        shieve2[itr] = 0
        itr += i

for i in range(257,50101):
    if shieve2[i]:
        prime.append(i+1)

while True:
    try:
        n = int(input())
        m = bisect.bisect(prime,n)
        if n==prime[m-1]:
            print(prime[m-2],prime[m])
        else:
            print(prime[m-1],prime[m])
    except EOFError:
        break

Submission status: Accepted

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, 0, -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: Accepted

Solution code:
primes = [0, 0] + [1]*50020
for i in range(2, 226):
    if primes[i]:
        for j in range(i*i, 50021, i):
            primes[j] = 0

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

Submission status: Accepted

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

from math import sqrt, ceil, pow
import bisect
import sys


# https://github.com/mccricardo/sieve_of_atkin/blob/master/sieve_of_atkin.py
class SieveOfAtkin:
    def __init__(self, limit):
        self.limit = limit
        self.primes = []
        self.sieve = [False] * (self.limit + 1)

    def flip(self, prime):
        try:
            self.sieve[prime] = True if self.sieve[prime] == False else False
        except KeyError:
            pass

    def invalidate(self, prime):
        try:
            if self.sieve[prime] == True: self.sieve[prime] = False
        except KeyError:
            pass

    def isPrime(self, prime):
        try:
            return self.sieve[prime]
        except KeyError:
            return False

    def getPrimes(self):
        testingLimit = int(ceil(sqrt(self.limit)))

        for i in range(testingLimit):
            for j in range(testingLimit):
                # n = 4*i^2 + j^2
                n = 4 * int(pow(i, 2)) + int(pow(j, 2))
                if n <= self.limit and (n % 12 == 1 or n % 12 == 5):
                    self.flip(n)

                # n = 3*i^2 + j^2
                n = 3 * int(pow(i, 2)) + int(pow(j, 2))
                if n <= self.limit and n % 12 == 7:
                    self.flip(n)

                # n = 3*i^2 - j^2
                n = 3 * int(pow(i, 2)) - int(pow(j, 2))
                if n <= self.limit and i > j and n % 12 == 11:
                    self.flip(n)

        for i in range(5, testingLimit):
            if self.isPrime(i):
                k = int(pow(i, 2))
                for j in range(k, self.limit, k):
                    self.invalidate(j)

        self.primes = [2, 3] + [x for x in range(len(self.sieve)) if self.isPrime(x) and x >= 5]
        return self.primes




def solve1(num, primes):
    #
    i = bisect.bisect_left(primes, num)
    lt = primes[i-1]
    i = bisect.bisect_left(primes, num+1)
    gt = primes[i]
    return lt, gt


if __name__ == '__main__':
    A = SieveOfAtkin(55000)
    A.getPrimes()
    # ??????????????\?????¨???????????????
    for line in sys.stdin:
        num = int(line)
        lt, gt = solve1(num, A.primes)
        print('{} {}'.format(lt, gt))

Submission status: Accepted

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

from math import sqrt, ceil, pow
import bisect
import sys


# https://github.com/mccricardo/sieve_of_atkin/blob/master/sieve_of_atkin.py
class SieveOfAtkin:
    def __init__(self, limit):
        self.limit = limit
        self.primes = []
        self.sieve = [False] * (self.limit + 1)

    def flip(self, prime):
        try:
            self.sieve[prime] = True if self.sieve[prime] == False else False
        except KeyError:
            pass

    def invalidate(self, prime):
        try:
            if self.sieve[prime] == True: self.sieve[prime] = False
        except KeyError:
            pass

    def isPrime(self, prime):
        try:
            return self.sieve[prime]
        except KeyError:
            return False

    def getPrimes(self):
        testingLimit = int(ceil(sqrt(self.limit)))

        for i in range(testingLimit):
            for j in range(testingLimit):
                # n = 4*i^2 + j^2
                n = 4 * int(pow(i, 2)) + int(pow(j, 2))
                if n <= self.limit and (n % 12 == 1 or n % 12 == 5):
                    self.flip(n)

                # n = 3*i^2 + j^2
                n = 3 * int(pow(i, 2)) + int(pow(j, 2))
                if n <= self.limit and n % 12 == 7:
                    self.flip(n)

                # n = 3*i^2 - j^2
                n = 3 * int(pow(i, 2)) - int(pow(j, 2))
                if n <= self.limit and i > j and n % 12 == 11:
                    self.flip(n)

        for i in range(5, testingLimit):
            if self.isPrime(i):
                k = int(pow(i, 2))
                for j in range(k, self.limit, k):
                    self.invalidate(j)

        self.primes = [2, 3] + [x for x in range(len(self.sieve)) if self.isPrime(x) and x >= 5]
        return self.primes




def solve1(num, primes):
    #
    i = bisect.bisect_left(primes, num)
    lt = primes[i-1]
    i = bisect.bisect_right(primes, num)
    gt = primes[i]
    return lt, gt


if __name__ == '__main__':
    A = SieveOfAtkin(55000)
    A.getPrimes()
    # ??????????????\?????¨???????????????
    for line in sys.stdin:
        num = int(line)
        lt, gt = solve1(num, A.primes)
        print('{} {}'.format(lt, gt))

Submission status: Accepted

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(50500)

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

Submission status: Accepted

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)
    if n == 3:
      print(2, end=" ")
    else:
      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: Accepted

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

# Sieve of Eratosthenes
N = 50021
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)

# solve
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: Accepted

Solution code:
import sys
import math

# Sieve of Eratosthenes
N = 50021
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)

# solve
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: Accepted

Solution code:
n = 50021
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 < 50021 and b == 0 and c[n + i - 1] == 1:
                b = n + i
        print(a,b)
    except:
        break

Submission status: Accepted

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

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

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

N = list(get_input())
for l in range(len(N)):
    n = int(N[l])
    d = 1
    while True:
        if primes[n-d]:
            print(n-d, end=" ")
            break
        d += 1

    d = 1
    while True:
        if primes[n+d]:
            print(n+d)
            break
        d += 1

Submission status: Accepted

Solution code:
MAX = 60000
lst = [i for i in range(MAX)]
lst[0] = lst[1] = 0
for i in range(MAX):
  if lst[i] != 0:
    for j in range(i * 2, MAX, i):
      lst[j] = 0
while 0 == 0:
  try:
    n = int(input())
    i = n - 1
    j = n + 1
    while lst[i] == 0:
      i -= 1
    while lst[j] == 0:
      j += 1
    print(str(lst[i]) + " " + str(lst[j]))
  except EOFError:
    break

Submission status: Accepted

Solution code:
MAX = 60000
lst = [i for i in range(MAX)]
lst[0] = lst[1] = 0
for i in range(MAX):
  if lst[i] != 0:
    for j in range(i * 2, MAX, i):
      lst[j] = 0
while 0 == 0:
  try:
    n = int(input())
    i = n - 1
    j = n + 1
    while lst[i] == 0:
      i -= 1
    while lst[j] == 0:
      j += 1
    print(lst[i],lst[j])
  except EOFError:
    break

Submission status: Accepted

Solution code:
import sys
for e in sys.stdin:
 a=b=int(e)
 while 1:
  a-=1
  if 2 in[a,pow(2,a,a)]:break
 while 1:
  b+=1
  if 2 in[b,pow(2,b,b)]:break
 print(a,b)

Submission status: Accepted

Solution code:
import sys
def is_prime(x):
 if x<=1:return False
 i=2
 while i*i<=x:
  if x%i==0:return False
  i+=1
 return True
for e in sys.stdin:
 N=int(e)
 mx=mn=0
 for i in range(N-1,1,-1):
  if is_prime(i):mx=i;break
 for i in range(N+1,N*2):
  if is_prime(i):mn=i;break
 print(mx,mn)

Submission status: Accepted

Solution code:
a = [0, 0, 1, 1] + [0, 1] * 25009
for i in range(3, 50022, 2):
    if a[i]:
        for j in range(2, 50021 // i + 1):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: Accepted

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 - 1], primes[ind])

  except EOFError:
    break

Submission status: Accepted

Solution code:
import bisect

MAX = 50050

#エラトステネスの篩
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 - 1], primes[ind])

  except EOFError:
    break

Submission status: Accepted

Solution code:
# AOJ 0044 Prime Number II
# Python3 2018.6.16 bal4u

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 itertools import chain
from bisect import bisect_left

max_n = 50022
primes = {2,3} | {m for n in (5, 7) for m in range(n, max_n, 6)}
du = primes.difference_update
for n in chain(range(5, max_n, 6), range(7, max_n, 6)):
    if n in primes:
        du(range(n*3, max_n, n*2))

primes = tuple(primes)

try:
    while True:
        n = int(input())
        i = bisect_left(primes, n)
        print(primes[i-1], primes[i+(n==primes[i])])
except EOFError:
    exit()

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


if __name__ == "__main__":
    all_primes = primes(60000)
    while True:
        try:
            n = int(input())
            ps = primes(n)
            x = ps[-1] if ps[-1] != n else ps[-2]
            y = all_primes[len(ps)]
            print("{} {}".format(x, y))
        except:
            break

Submission status: Accepted

Solution code:
import sys
n=10**6
p=[True]*n
p[0],p[1]=False,False
for i in xrange(2,int(n**0.5)+1):
    if p[i]==True:
        for j in xrange(i**2,n,i):
            p[j]=False
gr,le=[None]*n,[None]*n
prime=None
for i in xrange(n-1,-1,-1):
    gr[i]=prime
    if p[i]:
        prime=i
for i in xrange(0,n):
    le[i]=prime
    if p[i]:
        prime=i
for line in sys.stdin.readlines():
    num=int(line.strip())
    print le[num],gr[num]

Submission status: Accepted

Solution code:
import math
p = [2]
s = 3
max = 50000

while p[len(p)-1] <= max:
    m = int(math.sqrt(s))
    r = True
    for i in p:
        if i > m:
            break
        if s % i == 0:
            r = False
            break
    if r:
        p.append(s)
    s += 2

while True:
    try:
        n = int(raw_input())
    except EOFError as e:
        break
    i = 0
    while p[i] < n:
        i += 1
    print("%d %d" % (p[i-1], p[i+1] if p[i] == n else p[i]))

Submission status: Accepted

Solution code:
import math
p = [2]
s = 3
max = 50000
last = 0

while p[last] <= max:
    m = int(math.sqrt(s))
    r = True
    for i in p:
        if i > m:
            break
        if s % i == 0:
            r = False
            break
    if r:
        p.append(s)
        last += 1
    s += 2

while True:
    try:
        n = int(raw_input())
    except EOFError as e:
        break
    i = 0
    while p[i] < n:
        i += 1
    print("%d %d" % (p[i-1], p[i+1] if p[i] == n else p[i]))

Submission status: Accepted

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+=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: Accepted

Solution code:

import sys


primes = [2]

def solv(num):
    p1 = 0
    p2 = 0
    if num < primes[-1]:
        p1 = filter(lambda x: x < num, primes)[-1]
        lis = filter(lambda x: num < x, primes)
        if lis:
            p2 = lis[0]
    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: Accepted

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
        if p < n:
            under = p
    print(under, upper)

Submission status: Accepted

Solution code:
import sys

p = [True] * (55000)
p[0] = p[1] = False
for i in range(2, 55000):
    if p[i]:
        for j in range(i * 2, 55000, 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: Accepted

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:
    try:
        n = input()
        print pm[n],pM[n]
    except EOFError:
        break

Submission status: Accepted

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(50100)
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: Accepted

Solution code:
import math

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

n=10000
primes=get_primes(50100)
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: Accepted

Solution code:
import math

r = 50021
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,r):
            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: Accepted

Solution code:
import math

n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
    
r = max(n)+100
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

for a in n:
    for i in range(a,r):
       if p[i] == 1:
            lp = i+1
            break
    for i in range(a-2,0,-1):
        if p[i] == 1:
            sp = i+1
            break
    print sp, lp

Submission status: Accepted

Solution code:
import sys 
def primes(m):
    N = range(1,m+1,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)
    x = [2] + filter(None,N)
    return x
 

PRIMES = primes(50100)
for s in sys.stdin:
    n = int(s)
    for a in PRIMES:
        if a>n: break
        elif a<n: b = a
    print b,a

Submission status: Accepted

Solution code:
import sys 
def sieves(m):
    N = range(1,m+1,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 N

S = sieves(50100)
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: Accepted

Solution code:
import sys
def primes(m):
    N = range(1,m+1,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)
    x = [2] + filter(None,N)
    return x

PRIMES = primes(50030)
for s in sys.stdin:
    n = int(s)
    for a in PRIMES:
        if a>n: break
        elif a<n: b = a
    print b,a

Submission status: Accepted

Solution code:
import sys
def primes(m):
    N = range(1,m+1,2)
    r = int(m**.5)
    h = len(N)
    N[0] = 0
    i=0
    while 1:
        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)
        i += 1
    x = [2] + filter(None,N)
    return x

PRIMES = primes(50030)
for s in sys.stdin:
    n = int(s)
    for a in PRIMES:
        if a>n: break
        elif a<n: b = a
    print b,a

Submission status: Accepted

Solution code:
import sys
def primes(m):
    N = range(1,m+1,2)
    r = int(m**.5)
    h = len(N)
    N[0] = 0
    i=0
    while N[i]<=r:
        x = N[i]
        if x and i+x<h: N[i+x:h:x] = [0]*((h-1-i-x)/x+1)
        i += 1
    x = [2] + filter(None,N)
    return x

PRIMES = primes(50030)
for s in sys.stdin:
    n = int(s)
    for a in PRIMES:
        if a>n: break
        elif a<n: b = a
    print b,a

Submission status: Accepted

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(90000)
    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: Accepted

Solution code:
def sieve(n):
    primes = [True] * n
    primes[0] = primes[1] = False
    for i in xrange(2, int(n ** 0.5) + 1):
        if primes[i]:
            for j in xrange(i * i, n, i):
                primes[j] = False
    return [i for i in xrange(n) if primes[i]]

while 1:
    try:
        n = input()
    except EOFError:
        break
    primes = sieve(n * 2)
    small, big = -1, -1
    for prime in primes:
        if prime < n:
            small = prime
        if prime > n:
            big = prime
            break
    print small, big

Submission status: Accepted

Solution code:
N = 50030
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: Accepted

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

Submission status: Accepted

Solution code:
import math

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

prime_list = []
for i in range(2,50022):
    if prime(i)==1:
        prime_list.append(i)
while True:
    try:
        n = int(input())
    except:
        break
    print(max([x for x in prime_list if x < n]), end=' ')
    print(min([x for x in prime_list if x > n]))

Submission status: Accepted

Solution code:
lst = [1]*50021
for i in range(50021):
    if i == 0:
        lst[i] = 0
    else:
        if lst[i] == 1:
            j = i +1
            k = i
            while True:
                k = k + j
                if k >= 50021:
                    break
                        
                lst[k] = 0

while True:
    try:
        n = int(input())
        a = lst[0:n-1]
        b = lst[n:]
        print((n - 1 - a[::-1].index(1)),(n + 1 + b.index(1)))

    except EOFError:
        break