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

X = int(input())


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


while not is_prime(X):
    X += 1

print(X)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
X = int(stdin.readline().rstrip())
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data

d = np.array(get_sieve_of_eratosthenes(200000))
print(min(d[d >= X]))

Submission status: Accepted

Solution code:

def prime_factorize(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


X = int(input())

while True:
    x = prime_factorize(X)
    if len(x) == 1:
        print(X)
        break
    else:
        X += 1

Submission status: Accepted

Solution code:
import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

X = int(input())

for i in range(100000):
    if isPrime(X + i):
        print(X+i)
        break

Submission status: Accepted

Solution code:
X=int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

for x in range(X, 10**6+1):
    divisors = make_divisors(x)
    if len(divisors)==2:
        print(x)
        exit()

Submission status: Accepted

Solution code:
import math


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

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

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

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import bisect

N= one_int()

import math
def AtkinSieve (limit):
    results = [2,3,5]
    sieve = [False]*(limit+1)
    factor = int(math.sqrt(limit))+1
    for i in range(1,factor):
        for j in range(1, factor):
            n = 4*i**2+j**2
            if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
                sieve[n] = not sieve[n]
            n = 3*i**2+j**2
            if (n <= limit) and (n % 12 == 7):
                sieve[n] = not sieve[n]
            if i>j:
                n = 3*i**2-j**2
                if (n <= limit) and (n % 12 == 11):
                    sieve[n] = not sieve[n]
    for index in range(5,factor):
        if sieve[index]:
            for jndex in range(index**2, limit, index**2):
                sieve[jndex] = False
    for index in range(7,limit):
        if sieve[index]:
            results.append(index)
    return results

temp = AtkinSieve(10**5+4)

index=bisect.bisect_right(temp,N)

if temp[index-1]==N:
    print(N)
else:
    print(temp[index])

Submission status: Accepted

Solution code:
x = int(input())

def Prime(n):
    for p in range(2, n):
        if n % p == 0:
            return 0
    return 1

for i in range(x, 10 ** 8):
    sosu = Prime(i)
    if sosu == 1:
        print(i)
        break

Submission status: Accepted

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

x = int(input())
while True:
    if make_divisors(x):
        print(x)
        exit()
    x += 1

Submission status: Accepted

Solution code:
import math

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):
        break
    else:
        X += 1

print(X)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

if N==2:
    print(2)
    exit()

for i in range(N,10**5+10):
    flag=True
    for j in range(2,-int((-(i**0.5)//1))+1):
        if i%j==0:
            flag=False
            break
    if flag:
        print(i)
        exit()

Submission status: Accepted

Solution code:
X=int(input())
dp=[True]*(10**5+10000)
dp[0]=False
dp[1]=False
for i in range(2,len(dp)):
  if dp[i]:
    for j in range(i*2,len(dp),i):
      dp[j]=False
      
for i in range(X,len(dp)):
  if dp[i]:
    print(i)
    break

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table
ps = sieve(10 ** 6)
x = bl(ps[1], N)
print(ps[1][x])

Submission status: Accepted

Solution code:
import math

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())
for i in range(x,x+10**5):
  if is_prime(i)==True:
    break
print(i)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table


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

    table = sieve(10**6)
    for p in table:
        if p >= X:
            print(p)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

f = False

index = N-1
while f == False:
    index += 1
    f = is_prime(index)

print(index)

Submission status: Accepted

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True

p = None
XY = None
N = None


def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return is_prime


def main():
    X = I()
    a = primes(10**5+1000)

    for i in range(0, 10**5+1000+1):
        if i >= X and a[i] == 1:
            print(i)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
X=int(input())

p=[True]*(X*100)
p[0]=False
p[1]=False
for i in range(2,X*100):
    if p[i]:
        if i>=X:
            print(i)
            break
        for j in range(2*i, X*100, i):
            p[j]=False

Submission status: Accepted

Solution code:
import sys
X = int(input())
N = X
def num(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
while True:
    if num(N) != False:
        print(N)
        sys.exit()
    else:
        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 True
    return False
  
x = int(input())

while(True):
  if (trial_division(x)):
    x += 1
  else:
    break

print(x)

Submission status: Accepted

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

while True:
    i = 2
    flag = 0
    while i * i <= x:
        if x % i == 0:
            flag = 1
            break
        i += 1
    if flag == 0:
        print(x)
        exit()
    x += 1

Submission status: Accepted

Solution code:
from math import ceil,sqrt
X = int(input())
for i in range(X,10**6):
    for j in range(2,ceil(sqrt(i))):
        if i%j == 0:
            break
    else:
        print(i)
        exit()

Submission status: Accepted

Solution code:
import math
X = int(input())
f = True
while (True):
    f = True
    for j in range(2,int(math.sqrt(X))+1):
        if (X % j == 0):
            f = False
    if (f):
        break
    X += 1

print(X)

Submission status: Accepted

Solution code:
import math

def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)
        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

X = int(input())
for p in get_primenumber(100003):
    if p >= X:
        print(p)
        break

Submission status: Accepted

Solution code:
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    x = int(input())
    while True:
        if is_prime(x):
            print(x)
            break
        x += 1

Submission status: Accepted

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


def main():
    x = int(input())
    i = 0
    while True:
        ans = sosu(x)
        if ans == True:
            print(x)
            return
        x += 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

x = int(input())
while True:
    if is_prime3(x):
        print(x)
        break
    else:
        x += 1

Submission status: Accepted

Solution code:
n = int(input())

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


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

Submission status: Accepted

Solution code:
N = int(input())
answer = N
while 1:
    if all([answer%n for n in range(2,answer)]):
        print(answer)
        exit()
    else:
        answer += 1

Submission status: Accepted

Solution code:
x = int(input())

#引数nが素数かどうかを判定
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

ans = x

for i in range(x,10**10):
    if is_prime(i) == True:
        break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def is_prime(n):
    '''
    素数判定する
    '''
    if n == 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


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

Submission status: Accepted

Solution code:
import sys
import collections
import numpy as np
input = sys.stdin.readline
X = int(input())
import math

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
while True:
    if is_prime(X):
        print(X)
        sys.exit()
    X += 1

Submission status: Accepted

Solution code:
def is_prime(n):
    for k in range(2,int(n**0.5)+1):
        if n%k==0:
            return False
    return True
x=int(input())
while not is_prime(x):
    x+=1
print(x)

Submission status: Accepted

Solution code:
def is_prime2(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

c = int(input())
for i in range(c, 10**6):
    if is_prime2(i):
        print(i)
        break

Submission status: Accepted

Solution code:
import math
x = int(input())
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
if x == 2:
    print(x)
    exit()
elif x % 2 == 0:
    x += 1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
X = int(input())

def factorize(target_number):
    factor = 2
    factor_list = []
    while factor * factor <= target_number:
        while target_number % factor == 0:
            target_number //= factor
            factor_list.append(factor)
        factor = factor + 1
    if target_number > 1:
        factor_list.append(target_number)
    return factor_list

ans = 0
for i in range(X, 100003 + 1):
    if len(factorize(i)) == 1:
        ans = i
        break

print(ans)

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):
    # 確かめるのはnの平方根までで大丈夫
        if not is_prime[i]:  # すでにfalseなら次のiへ
            continue
            """
            bool(not False)はTrueになる
            """
        for j in range(i * 2, n + 1, i):
        # iずつ大きくなる(つまりiの倍数をみる)
            is_prime[j] = False
            # i自身を除くiの倍数を全てFalseにする
    return [i for i in range(n + 1) if is_prime[i]]
     # Trueのものだけ列挙して返す


N = int(input())
hoge = primes(10**6)
for i in range(len(hoge)):
    if hoge[i] >= N:
        print(hoge[i])
        exit()

Submission status: Accepted

Solution code:
X = int(input())

prime = [True] * (100010)

prime[0] = False;
prime[1] = False;
for i in range(4,100010,2):
    prime[i] = False

i = 3
while(i*i<=100008):
    if prime[i]:
        for j in range(i+i,100008,i):
            prime[j] = False
    i += 2

for i in range(X,100008):
    if prime[i]:
        print(i)
        break

Submission status: Accepted

Solution code:
x = int(input())


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

print(x)

Submission status: Accepted

Solution code:
import math
X=int(input())
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
while True:
    if is_prime(X):
        ans = X
        break
    X += 1
print(ans)

Submission status: Accepted

Solution code:
def prime(x):
    a = 0
    for i in range(2, int(x**0.5)):
        if x % i == 0:
            a = 1
    return a

X = int(input())

while True:
    b = prime(X)
    if b == 0:
        print(X)
        exit()
    X += 1

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 is_prime

X = int(input())
Y = X + 10000

P = primes(Y)

k = 0
while True:
    if P[X+k]==True:
        print(X+k)
        break
    k += 1

Submission status: Accepted

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

import math
P = [2]
for k in range(3,100010):
    f = 1
    for l in range(2,int(math.sqrt(k))+1):
        if k % l == 0:
            f = 0
            break
    if f==1:
        P.append(k)

print(P[bisect.bisect_left(P,N)])

Submission status: Accepted

Solution code:
import numpy as np


def solve(x):
    primes_flag = np.ones(10 ** 6).astype(np.int)
    primes_flag[:2] = 0
    for p in range(10 ** 3):
        if primes_flag[p] == 1:
            primes_flag[p ** 2:10 ** 6:p] = 0
    for i in range(x, 10 ** 6):
        if primes_flag[i] == 1:
            return i
    return 0


def main():
    x = int(input())
    res = solve(x)
    print(res)


def test():
    assert solve(20) == 23
    assert solve(2) == 2
    assert solve(99992) == 100003


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
INF = 10 ** 5 + 5
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return
eratorasu()
X = int(input())
for i in range(X, INF):
    if is_prime[i] == 1:
        print(i)
        exit()

Submission status: Accepted

Solution code:
def getIsPrimes(n):
    isPrimes = [False]*2 + [True]*(n-1)
    for i in range(2, int(n**0.5)+1):
        if isPrimes[i]:
            for x in range(i*i, n+1, i):
                isPrimes[x] = False
    return isPrimes

X = int(input())

isPrimes = getIsPrimes(10**6)

for i in range(X, 10**6):
    if isPrimes[i]:
        print(i)
        break

Submission status: Accepted

Solution code:
X = int(input())

def eratosthenes(n):
    res = []
    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
    for i in range(n+1):
        if is_prime[i]:
            res.append(i)
    return res

li = eratosthenes(10**6)
for ele in li:
    if ele >= X:
        print(ele)
        exit()

Submission status: Accepted

Solution code:
import bisect

x = int(input())
n = 10 ** 5 + 10
fl = [1] * n
fl[0] = 0
fl[1] = 0
lprime = []
for i in range(n):
    if fl[i] == 1:
        lprime.append(i)
        ti = i * 2
        while ti < n:
            fl[ti] = 0
            ti += i

res = lprime[bisect.bisect_left(lprime, x)]
print(res)

Submission status: Accepted

Solution code:
def sieve(n):
    is_prime = [True for _ in range(n + 1)]
    is_prime[0] = False

    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = 2 * i
            while j <= n:
                is_prime[j - 1] = False
                j += i
    table = [i for i in range(1, n + 1) if is_prime[i - 1]]
    return is_prime, table


X = int(input())
table = sieve(100003 + 100)[1]
for t in table:
    if t >= X:
        print(t)
        break

Submission status: Accepted

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        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]]

n = int(input())
prime_list = prime(110000)
i = 0
while True:
    if prime_list[i] >= n:
        print(prime_list[i])
        break
    else:
        i += 1

Submission status: Accepted

Solution code:
import math

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)
        exit()
    else:
        X += 1

Submission status: Accepted

Solution code:
def sieve(n):
    s = [True for _ in range(n + 1)]
    for i in range(2, int(n ** 0.5) + 1):
        if s[i]:
            for j in range(i * 2, len(s), i):
                s[j] = False
    return (i for i in range(n + 1) if s[i] and i > 1)


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

    p = list(sieve(x * 2))
    for a in p:
        if a >= x:
            print(a)
            break

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

x = I()

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 bisect

def generate_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]]

def solve():
  X = int(input())
  primes = generate_primes(10 ** 5 + 100)
  index = bisect.bisect_left(primes, X)
  return primes[index]

print(solve())

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools

def sRaw():
    return input().rstrip("\r")

def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


DIV = 998244353

def main():
    X = iRaw()
    Y=X
    while True:
        Z = 2
        mayPrime = True
        while Z*Z <=Y:
            if Y%Z==0:
                mayPrime=False
                break
            Z+=1
        if mayPrime:
            return Y
        Y+=1
    

if __name__ == "__main__":

    print(main())

Submission status: Accepted

Solution code:
import math
import bisect
import collections
import itertools
def gcd(a,b):return math.gcd #最大公約数
def lcm(a,b):return (a*b) // math.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

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 = iin()

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

Submission status: Accepted

Solution code:
n=100004
prime=[False]*2+[True]*(n-2)
for i in range(2,n):
  if prime[i]:
    for j in range(i*2,n,i):
      prime[j]=False
s = [i for i in range(2,n) if prime[i]]
x=int(input())
import bisect as bi
print(s[bi.bisect_left(s,x)])

Submission status: Accepted

Solution code:
X=int(input())
S=[1 for i in range(10**6+1)]
S[1]=0
for i in range(2,10**6):
    if S[i]==1:
        for j in range(2,10**6):
            if i*j<=10**6:
                S[i*j]=0
            else:
                break
for i in range(X,10**6):
    if S[i]==1:
        print(i)
        exit()

Submission status: Accepted

Solution code:
x = int(input())
k = 0
while k == 0:
    x_ = int(x**(1/2))
    for i in range(x_, 1, -1):
        if x % i == 0:
            x += 1
            break
    else:
        k = 1
print(x)

Submission status: Accepted

Solution code:
from math import sqrt


def is_prime(num):
    if num < 2:
        return False

    for i in range(2, int(sqrt(num)) + 1):
        if num % i == 0:
            return False

    return True


x = int(input())

while not is_prime(x):
    x += 1

print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


def main():
    X = int(input())
    while True:
        if is_prime(X):
            break
        X += 1

    print(X)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
X = int(input())

import math

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

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

Submission status: Accepted

Solution code:
def main():
    X = int(input())

    def Eratosthenes(x: int) -> set:
        """x以下の素数の集合を返す"""
        import math
        sup = int(x)
        primes = {i for i in range(2, sup+1)}
        for i in range(2, int(math.sqrt(sup+1))+1):
            if i in primes:
                mul = 2
                while i*mul <= sup:
                    primes.discard(i*mul)
                    mul += 1
        return primes
    p = Eratosthenes(100003)
    m = 1 << 60
    for i in p:
        if X <= i and i < m:
            m = i
    print(m)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes

X = int(input())
p = sorted(list(prime_set(10**5 + 10)))
print(p[bisect.bisect_left(p, X)])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

x=I()
for i in range(x,x*100):
    fl=True
    for j in range(2,int(x**0.5)+1):
        if i%j==0:
            fl=False
            break
    if fl:
        print(i)
        exit()