Problem:


Score: 300 points

Problem Statement

Find the minimum prime number greater than or equal to X.

Notes

A prime number is an integer greater than 1 that cannot be evenly divided by any positive integer except 1 and itself.

For example, 2, 3, and 5 are prime numbers, while 4 and 6 are not.

Constraints

 2 \le X \le 10^5 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X

Output

Print the minimum prime number greater than or equal to X.

Sample Input 1

20

Sample Output 1

23

The minimum prime number greater than or equal to 20 is 23.

Sample Input 2

2

Sample Output 2

2

X itself can be a prime number.

Sample Input 3

99992

Sample Output 3

100003



Sample input:
20


Sample output:
23

Submission status: Accepted

Solution code:
def waru(x):
  for i in range(2, x):
    if x%i==0:
      return 1
    if i==x-1:
      return 2
x=input()
x=int(x)
while True:
  if waru(x)==1:
    x+=1
  else:
    print(x)
    break

Submission status: Accepted

Solution code:
import math
x = int(input())
n = x
while True:
  isPrime = True
  for i in range(2, int(math.sqrt(n))):
    if n % i == 0:
      isPrime = False
      break
  if isPrime:
    print(n)
    break
  n += 1

Submission status: Accepted

Solution code:
def f(n):
  ans = 0
  for i in range(2, n // 2):
    if ans == 0:
      if n % i == 0:
        ans = 1
        break
      else:
        next
  return ans

x = int(input())
ans = 0
while ans == 0:
  if f(x) == 1:
    x += 1
  elif f(x) == 0:
    ans = x
    break
print(ans)

Submission status: Accepted

Solution code:
import math
X = int(input())

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

while prime_judge(X)==False:
    X+=1
print(X)

Submission status: Accepted

Solution code:
x = int(input())

def q(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

l = 6
ans = 0
while l > 1:
    b = q(x)
    x += 1
    l = len(b)
print(x - 1)

Submission status: Accepted

Solution code:
x = int(input())
def prime(n):
    for i in range(2,n):
        if n%i == 0:
            return False
    return True
while True:
    if prime(x):
        print(x)
        break
    x += 1

Submission status: Accepted

Solution code:
import math

x = int(input())

while True:
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            break
    else:
        print(x)
        exit()
    x += 1

Submission status: Accepted

Solution code:
import math

X = int(input())

# √nまでで判定すればいい
def is_prime(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

while True:
    if is_prime(X):
        print(X)
        exit()

    X = X + 1

Submission status: Accepted

Solution code:
import numpy as np
def make_prime(U):
    is_prime = np.zeros(U,np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5)+1
    for p in range(3,M,2):
        if is_prime[p]:
            is_prime[p*p::p+p] = 0
    return is_prime, is_prime.nonzero()[0]

lst=make_prime(100004)
n=int(input())
if lst[0][n]==True:
    print(n)
else:
    flag=False
    while flag==False:
        n+=1
        if lst[0][n]==True:
            flag=True
    print(n)

Submission status: Accepted

Solution code:
def factorization(n):# 計算量O(√N)
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp]=1

    if arr==[]:
        arr[n] = 1

    return arr



x = int(input())
while(True):
    p = factorization(x)
    if (len(p)==1) & (x in p):
        break
    else:
        x += 1

print(x)

Submission status: Accepted

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter

## input

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]

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

X = int(input())

if X == 2:
    print(X)
    sys.exit()

if X%2 == 0:
    tmp = X + 1
else:
    tmp = X

for i in range(50000):
    if is_prime(tmp):
        print(tmp)
        sys.exit()
    else:
        tmp = tmp + 2

Submission status: Accepted

Solution code:
def resolve():
    import math
    X = int(input())
    while True:
        count = 0
        for i in range(2, int(math.sqrt(X))):
            if X%i == 0:
                count += 1
                break
        if count == 0:
            print(X)
            exit()
        else:
            X += 1
resolve()

Submission status: Accepted

Solution code:
import math

x = int(input())
p = 1
flag = 0

while flag == 0:
    p = 1
    for i in range(2, int(math.sqrt(x))):
        if x % i == 0:
            p = 0
            break
    if p == 0:
        x += 1
    else:
        flag = 1

print(x)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def main():
    x = int(input())

    sosuu_list = []
    for i in range(2, int(x ** 0.5) + 1):
        flg = 1
        for ele in sosuu_list:
            if i % ele == 0:
                flg = 0
                break
        if flg:
            sosuu_list.append(i)

    while 1:
        flg = 0
        for ele in sosuu_list:
            if x % ele == 0:
                flg = 1
                break
        if flg:
            x += 1
        else:
            break

    print(x)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import math

input=stdin.readline

def isPrime(x):
  if x % 2 == 0:
    return False
  for div in range(3, math.floor(x **(0.5)) + 1,2):
    if x % div == 0:
      return False

  return True

X = int(input())
if X == 2:
  print(2)
  exit()

if X % 2 == 0:
  X+=1

if isPrime(X):
   print(X)
   exit()

while (True):
  X += 2
  if isPrime(X):
    print(X)
    exit()

Submission status: Accepted

Solution code:
from sys import stdin

input=stdin.readline

def isPrime(x):
  for div in range(2, x // 2 + 1):
    if x % div == 0:
      return False

  return True

X = int(input())

if isPrime(X):
   print(X)
   exit()

while (X < 10 ** 5):
  X+=1
  if isPrime(X):
    print(X)
    exit()

#100000より大きい素数のうち最小のもの
print(100003)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
INF = 10**9

def is_prime(x):
    if x <= 1:
        return False
    for i in range(2,int(x**1/2)):
        if x%i == 0:
            return False
    return True

def main():
    x = int(input())
    n = x
    while not is_prime(n):
        n += 1
    print(n)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
def check(i):
    sqrt = round(i ** 0.5 + 0.5)
    for j in range(2, sqrt + 1):
        if not i % j:
            return False
    return True
while True:
    if n == 2:
        print(2)
        break
    if check(n):
        print(n)
        break
    n += 1

Submission status: Accepted

Solution code:
import math

def trial_division(target):
    dest = int(math.sqrt(target))
 
    for i in range(2,dest):
        if target % i == 0:
            return "NO"
    return "YES"
    
x = input()
x = int(x)

if trial_division(x) == "YES":
	print(int(x))
else:
	while trial_division(x) == "NO":
		x += 1
	else:
		print(x)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

X = int(input())

for i in range(X, 10 ** 6):
    check = factorization(i)
    l = len(check)
    if l == 1 and check[0][1] == 1:
        print(i)
        exit()

Submission status: Accepted

Solution code:
import math

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

x = int(input())
if x != 2 and x%2 == 0:
    x += 1

while True:
    if is_prime(x):
        print(x)
        break
    else:
        x += 2

Submission status: Accepted

Solution code:
X = int(input()) 

while(1):
  if X == 2:
    break
  for i in range(2,X):
    if X%i == 0:
      X += 1
      break
  if i == X-1:
      break

print(X)

Submission status: Accepted

Solution code:
import sys
X = int(input())
    
i = X
while True:
    if i == 2:
        print(i)
        sys.exit()
    elif i % 2 != 0:
        y = 3
        while True:
            if i == y:
                print(i)
                sys.exit()
            elif i % y == 0:
                break
            else:
                y += 2
    i += 1

Submission status: Accepted

Solution code:
x=int(input())
import math
y=0
if x==2:
  y=2
else:
  while y==0:
    if x % 2 ==0:
      x+=1
      continue
    else:
      c=0
      for i in range(3,int(math.sqrt(x))):
        if x % i == 0:
          c+=1
      if c ==0:
        y=x
        break
      else:
        x+=1
print(y)

Submission status: Accepted

Solution code:
import math
import bisect


def primelist(N):
    prime = [2]
    for i in range(3, N+1):
        flag = 1
        for j in prime:
            if i % j == 0:
                flag = 0
                break
        if flag == 1:
            prime.append(i)
    return prime


X = int(input())
primes = primelist(110000)

print(primes[bisect.bisect_left(primes, X)])

Submission status: Accepted

Solution code:
x = int(input())
while True:
    i = 2
    while i * i <= x:
        if x % i == 0:
            break
        i += 1
    else:
        print(x)
        exit()
    x += 1

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    x = int(input())
    if x == 2:
        print(x)
    else:
        while True:
            for i in range(2, x):
                if x % i == 0:
                    break
                if i == x-1:
                    print(x)
                    return
            x += 1

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import sys

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


n = int(input())

prime_list = get_sieve_of_eratosthenes(10**5*2)
#print(prime_list)
for p in prime_list:
  if p>=n:
    print(p)
    sys.exit()

Submission status: Accepted

Solution code:
X = int(input())

def is_prime(x):
  if x < 2: return False
  if x == 2 or x == 3 or x == 5: return True
  if x%2==0 or x%3==0 or x%5==0: return False

  prime = 7
  step = 4
  while prime <= int(p**0.5)+1:
    if x % prime == 0: return False
    prime += step
    step = 6-step

  return True

p = X
while True:
  if is_prime(p):
    print(p)
    exit()
  else:
    p += 1

Submission status: Accepted

Solution code:
x=int(input())

flag=0
for i in range(x,10**18):
  for p in range(2,i):
    if i%p==0:
      break
  else:
    print(i)
    break

Submission status: Accepted

Solution code:
import math
def is_prime(n):
  frag = 1
  if(n == 2 or n == 3):
    return True
  elif(n==4):
    return False
  else:
    for i in range(2, int(math.sqrt(n))+1):
      if(n % i == 0):
        frag = 0
  return frag == 1

n = int(input())
while(not(is_prime(n))):
  n += 1
print(n)

Submission status: Accepted

Solution code:

import math
def prime(n):
    for i in range(2, int(math.sqrt(n))):
        if n % i == 0: return False
    return True
 
X = int(input())
 
for i in range(X, 10**8):
    if prime(i):
        print(i)
        exit(0)
 
print('No prime number in this range')

Submission status: Accepted

Solution code:
def miller_rabin(n, k=100):
    import random
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for _ in range(k):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True
def main():
  x=int(input())
  for i in range(x,1000000):
    if miller_rabin(i):
      print(i)
      return
main()

Submission status: Accepted

Solution code:
def miller_rabin(n, k=10000):
    import random
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for _ in range(k):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True
def main():
  x=int(input())
  for i in range(x,1000000):
    if miller_rabin(i):
      print(i)
      return
main()

Submission status: Accepted

Solution code:
import math
def prime(n):
    for i in range(2, int(math.sqrt(n))):
        if n % i == 0: return False
    return True

X = int(input())

for i in range(X, 10**8):
    if prime(i):
        print(i)
        exit(0)

print('No prime number in this range')

Submission status: Accepted

Solution code:
x = int(input())

while True:
    i = 2
    while i ** 2 <= x:
        if x % i == 0:
            break
        i += 1
    if i ** 2 > x:
        break
    x += 1

print(x)

Submission status: Accepted

Solution code:
x=int(input())
while True:
  cnt=0
  for i in range(2,x//2):
    if x%i==0:
      cnt+=1
      break
  if cnt==0:
    print(x)
    break
  elif cnt==1:
    x+=1
    continue

Submission status: Accepted

Solution code:
x=int(input())
while True:
  cnt=0
  for i in range(2,x//2):
    if x%i==0:
      cnt+=1
      break
  if cnt==0:
    print(x)
    break
  else:
    x+=1
    continue

Submission status: Accepted

Solution code:
import math

def isPrime(n):
    if n == 2 or n == 3:
        return True
    if n%2 == 0:
        return False
    for i in range(3, int(math.sqrt(n))+1, 2):
        if n%i == 0:
            return False
    return True

X = int(input())
while True:
    if isPrime(X):
        print(X)
        break
    else:
        X += 1

Submission status: Accepted

Solution code:
X = int(input())
if X == 2:
    print(X)
    exit()
temp = 2
for i in range(X, 1000000):
    for j in range(2, X):
        if i % j == 0:
            break
        if j == X-1:
            print(i)
            exit()

Submission status: Accepted

Solution code:
import math
N=int(input())

count=4

S=[]
S.append(2)
S.append(3)

while count<110000:
    ser=int(math.sqrt(count))+1
    flag=True
    for i in range(2,ser+2):
        if count%i==0:
            flag=False
            break

    if flag==True:        
        S.append(count)
    count+=1
nagasa=len(S)
for i in range(nagasa):
    if N<=S[i]:
        print(S[i])
        exit()

Submission status: Accepted

Solution code:
from math import sqrt

N = 10 ** 6
# 初期値は全部trueでリストにセット
p = [True] * (N + 1)
# 2以上だから1以下はfalse
p[0] = False
p[1] = False
n = int(sqrt(N) + 1)
# 3の2ステップで奇数4の2ステップで偶数を潰す
# 素数がありえるとしたら奇数行だからそこでまたfor文
for j in range(4, N + 1, 2):
  p[j] = False
for i in range(3, n + 1, 2):
#   もしp[j]とかぶるものがあればfalse
  if p[i]:
    for j in range(i + i, N + 1, i):
      p[j] = False



X = int(input())
for i in range(X, N + 1):
    if p[i]:
        print(i)
        break

Submission status: Accepted

Solution code:
import math
def resolve():
    def is_prime(n):
        if n == 1:
            return False
 
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
 
        return True
    X = int(input())
 
    while True:
        if is_prime(X):
            print(X)
            return
        else:
            X += 1
 
    return
 
resolve()

Submission status: Accepted

Solution code:
X = int(input())
flg = 0
while 1:
  flg = 0
  for x in range(2, X // 2):
    if X % x == 0:
      X += 1
      flg = 1
      break
  if flg == 1:
    continue
  else:
    break
print(X)

Submission status: Accepted

Solution code:
x = int(input())
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True

while True:
    if isPrime(x) == False:
        x = x+1
    else:
        break
print(x)

Submission status: Accepted

Solution code:
import math
import sys

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

x=int(input())

while(1):
  if is_prime(x):
    print(x)
    sys.exit()
  x=x+1

Submission status: Accepted

Solution code:
limit = 100003
import math
def resolve():
    N = int(input())
    for k in range(N, limit+1):
        factor = 0
        if k % 2 == 0 and k != 2:
            continue
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1
        if factor == 0:
                return k
print(resolve())

Submission status: Accepted

Solution code:
n=int(input())
if n==2:print(2);exit()
if n==3:print(5);exit()
for i in range(n,n+111):
  for j in range(2,int(n**0.5)+1):
    if i%j ==0:
      break
    if j==int(n**0.5):
      print(i)
      exit()

Submission status: Accepted

Solution code:
x = int(input())
 
def isPrime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return 0
    return 1
  
while(1):
    if isPrime(x):
        print(x)
        break
    x += 1

Submission status: Accepted

Solution code:
X=int(input())

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

while(1):
    if isPrime(X):
        break
    X+=1
print(X)

Submission status: Accepted

Solution code:
X = int(input())

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

for i in range(X, 100100):
    if(is_prime(i)):
        print(i)
        exit()

Submission status: Accepted

Solution code:
import sys
import math
a=0
N=int(input())
i=N
if N==2:
  print(2)
  sys.exit()
elif N==3:
  print(3)
  sys.exit()
elif N==4:
  print(5)
  sys.exit()
elif N==5:
  print(5)
  sys.exit()
while True:
  c=int(math.sqrt(i))
  for j in range(2,c+1):
    if i%j==0:
      a+=1
      break
  if a==0:
    print(i)
    sys.exit()
  a=0
  i=i+1

Submission status: Accepted

Solution code:
import math

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

N = int(input())

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

Submission status: Accepted

Solution code:
X = int(input())

def isSosu(x):
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    for i in range(3, x - 1, 2):
        if x % i == 0:
            return False
    return True

while True:
    if isSosu(X):
        print(X)
        break
    X += 1

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def is_prime(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

n = int(readline())
while is_prime(n) != True:
    n += 1
print(n)

Submission status: Accepted

Solution code:
import math
def prim(x):
  for i in range(2,math.floor(math.sqrt(x))):
    if not x%i:
      return 0
  return 1

def np(x):
  while(1):
    if prim(x):
      return x
    else:
      x+=1
      
print(np(int(input())))

Submission status: Accepted

Solution code:
import math
n = int(input())

while True:
  flag = True
  
  for i in range(2, int(math.sqrt(n))+1):
    if n % i == 0: 
      flag = False
      break
  
  if flag: 
    print(n)
    break
  
  n += 1

Submission status: Accepted

Solution code:
import math
X = int(input())

while 1:
  flag = 1
  for i in range(2,int(math.sqrt(X))+1):
    if X % i == 0:
      flag = 0
      X += 1
      break
  if flag == 1:
    print(X)
    break

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 set([i for i in range(n + 1) if is_prime[i]])
sosuu = primes(10**6)
N=int(input())
for i in range(N,10**6):
 if i in sosuu:
  print(i)
  break

Submission status: Accepted

Solution code:
# 2253~
# 解法2259
# 1 素数のリストを作って，そのリストにおいてXより大きくなる最初の要素のインデックスを計算する
# 2 Xから増やしていって，素数かどうかの判定をする.最初に素数となるものを出力する.
# 1のほうがわかりやすいよね．素数のリストを作って，ソートする（勝手になっている）．残った素数に対してbisectで要素を見つけ出す
# 2313. ギブです．エラトステネスの古いがかけない．Pから減らしていくがpの要素を減らすので
# generatorとしてPを使うと途中でPの形が変わるのが問題になると思う

# 実装．エラトステネスの篩を実装すればいいことはわかるけどめんどくさい．
X=int(input())

MAX = X+10000
P = [2]
Rest = set(list(range(3,MAX,2)))
import math
MAX_ind = int(math.sqrt(X)) + 1

for i in range(3,MAX_ind+1,2):
    if i in Rest:
        P.append(i)
        for j in range(i,MAX,i):
            if j in Rest:
                Rest.remove(j)
# 残ったRestとPを合体させて，
Rest = list(Rest)
Rest.sort()

P = P + Rest

import bisect
# すでにsortされているので，それによってうまくいく.
ind = bisect.bisect_left(P,X)
print(P[ind])

Submission status: Accepted

Solution code:
def is_prime(n):
    if n==1:
        return False
    else:
        for i in range(2, int(n**0.5)+1):
            if n % i == 0:
                return False
    return True

x = int(input())

while not is_prime(x):
    x += 1

print(x)

Submission status: Accepted

Solution code:
import math
X = int(input())
if X == 2:
    print(2)
    exit()
elif X == 3:
    print(3)
    exit()
elif X == 4 or X == 5:
    print(5)
    exit()
elif X == 6 or X == 7:
    print(7)
    exit()
elif X == 8:
    print(11)
    exit()
a = X
while True:
    b = math.floor(a**0.5)
    for i in range(2,(b+1)):
        if a%i == 0:
            break
        if i == b:
            print(a)
            exit()
    a += 1

Submission status: Accepted

Solution code:
import sys
x = int(input())
for i in range(x,10**6):
    a = i-2
    c = 0
    for j in range(2,i):
        if i % j != 0:
            c += 1
    if a == c:
        print(i)
        sys.exit()