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:
x = int(input())

while True:
    for i in range(2, x - 1):

        if x % i == 0:
            x += 1
            break
    else:
        ans = x
        print(ans)
        exit()

Submission status: Accepted

Solution code:
X = int(input())
while(1):
  flag = True
  for i in range(2,int(X**0.5)+1):
    #print(X,i)
    if X % i == 0:
      flag = False
      break
  if flag:
    print(X)
    break
  else:
    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)
        break
    x += 1

Submission status: Accepted

Solution code:
import bisect

def sieve(n):
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]
      
x = int(input())

p = sieve(10**5+4)

index = bisect.bisect_left(p,x)

print(p[index])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(pow(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:
x=int(input())
while True:
    r = int(x ** .5)
    for i in range(2,r+1):
        if x%i == 0:
            break
    else:
        break
    x+=1
print(x)

Submission status: Accepted

Solution code:
def is_prime(n):
    """
    Assumes that n is a positive natural number
    """
    # We know 1 is not a prime number
    if n == 1:
        return False

    i = 2
    # This will loop from 2 to int(sqrt(x))
    while i*i <= n:
        # Check if i divides x without leaving a remainder
        if n % i == 0:
            # This means that n has a factor in between 2 and sqrt(n)
            # So it is not a prime number
            return False
        i += 1
    # If we did not find any factor in the above loop,
    # then n is a prime number
    return True

x = int(input())
if x % 2 == 0 and x != 2:
  x += 1
while not is_prime(x):
  x += 2
print(x)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://pashango-p.hatenadiary.org/entry/20090704/1246692091
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

def main():
    
    n = int(input())
    
    for j in range(1000000000):
        ans = is_prime3(n)
        if ans == True:
            print(n)
            break
        n += 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#149_C
x = int(input())
for i in range(x, 10**10):
    if all(i % j != 0 for j in range(2, int(i**0.5)+1)):
        print(i)
        break

Submission status: Accepted

Solution code:
from math import sqrt
n=int(input())
def judge(x):
	for i in range(2,int(sqrt(x))+1):
		if x%i == 0:
			return False
		else:
			continue
	return True
for i in range(n,1+10**6):
	if judge(i):
		print(i)
		exit(0)
	else:
		pass
print('error')

Submission status: Accepted

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    X=int(input())
    while True:
        # 素数リスト
        n = X
        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))
        if X in primes:
            print(X)
            break
        else:
            X+=1


resolve()

Submission status: Accepted

Solution code:
from sys import stdin
import math

x = int(stdin.readline().rstrip())

while True:
    flag = False
    for i in range(x):
        if i <= 1:
            continue
        if x % i == 0:
            flag = True
    if flag == False:
        print(x)
        break
    else:
        x += 1

Submission status: Accepted

Solution code:
def is_prime(num,X):
  flg=0
  for i in range(2,X):
    if(num%i==0):
      flg=1
      break
  if(flg==0):
    return True
  else:
    return False

X=int(input())
i=0
flg=0
while True:
  num=X+i
  if(is_prime(num,X)==True):
    print(num)
    break
  i+=1

Submission status: Accepted

Solution code:
n = int(input())
while True:#while分は条件がTrueである限り回り続ける＝永遠に回る
  for i in range(2, int(n**0.5)+1):#素数は√nまでで判定できる
    if n % i == 0:
      n += 1
      break
    else:
      continue
  else:
    print(n)
    exit()

Submission status: Accepted

Solution code:
import math
def is_prime(n):
    t=True
    for i in range(2,int(math.sqrt(n))+1):
        if(n%i)==0:
            t=False
            break
    return t
j=int(input())
while True:
    if(is_prime(j)):
        print(j)
        exit()
    j+=1

Submission status: Accepted

Solution code:
import math
N = int(input())
flag = 0
while flag == 0:
  lst = []
  for i in range(1, math.ceil(N**0.5)):
    if N%i == 0:
      if i**2 == N:
        lst.append(i)
      else:
        lst.append(i)
        lst.append(N//i)
  if len(lst) == 2:
    flag = 1
  else:
    N += 1
print(N)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 

mx = int(math.pow(10, 5) + 1000)

def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]

n = load()
plist = prime_list(mx)
for i in range(len(plist)):
    if plist[i] >= n:
        print(plist[i])
        exit()

Submission status: Accepted

Solution code:
from bisect import*
n=int(input())
def ERATOSTHENES(n):
    is_prime=[0,0]+[1]*(n-1)
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2,n+1,i):
                is_prime[j]=0
    return [k for k,v in enumerate(is_prime) if v]
    
x=ERATOSTHENES(10**6)
print(x[bisect_left(x,n)])

Submission status: Accepted

Solution code:
x = int(input())
while not all(x % i for i in range(2, x)):
    x += 1
print(x)

Submission status: Accepted

Solution code:
x = int(input())
i = x
while True:
  flag = True
  for j in range(2,int(i**(0.5))+1):
    if i%j == 0:
      i += 1
      flag = False
      break
  if flag:
    break  
print(i)

Submission status: Accepted

Solution code:
X = int(input())
if X == 2:
    print(2)
else:
    def f(n):
        for i in range(3, int(n**0.5)):
            if n % i == 0:
                return True
        return False

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

    while f(res):
        res += 2

    print(res)

Submission status: Accepted

Solution code:
X = int(input())


ans = X
if ans == 2:
    print(ans)
    exit()
while True:
    for i in range(2, ans):
        if ans % i == 0:
            ans += 1
            break
        elif i == ans - 1:
            print(ans)
            exit()

Submission status: Accepted

Solution code:
x=int(input())
i=0
while True:
    for j in range(2,x+i+1):
        if j==x+i:
            print(j) #ans
            quit()
            break
        elif (x+i)%j==0 and j!=1:
            break
    i+=1

Submission status: Accepted

Solution code:
X = int(input())

def prime(n):
  for i in range(2,n//2 + 1):
    if n % i == 0:
      return 0
  return n

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

Submission status: Accepted

Solution code:
import math
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np


x= int(input())
# p = list(map(int, input().split()))

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

    return a
ans = 0
while 1:
    if iss(x):
        ans = x
        break
    x += 1

print(ans)

Submission status: Accepted

Solution code:
import math

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

x = int(input())
for j in range(x,10**6):
    if prime_number(j) and x <= j:
        print(j)
        break

Submission status: Accepted

Solution code:
x = int(input())

while True:
    if any(x % i == 0 for i in range(2, (x // 2))):
        x += 1
    else:
        print(x)
        exit(0)

Submission status: Accepted

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

X = int(input())
Num = X

while any(Num%i==0 for i in range(2,Num)):
    Num += 1

print(Num)

Submission status: Accepted

Solution code:
import math


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


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

Submission status: Accepted

Solution code:
n = int(input())
for i in range(n, 100004):
    flag = 0
    for j in range(2, int(i**(1/2)) + 1):
        if i % j == 0:
            flag = 1
            break
    if flag == 0:
        print(i)
        break

Submission status: Accepted

Solution code:
x = int(input())

for i in range(x,10**7):
  ans = 0
  for j in range(2,int(i/2)):
    if  i % j == 0 :
      ans +=1
      
  if ans ==0:
    print(i)
    exit()

Submission status: Accepted

Solution code:

import math


def submit():
    x = int(input())
    max_prime = 100003
    sieve = [True for _ in range(max_prime + 1)]
    sieve[0] = False
    sieve[1] = False

    # 篩に掛ける
    cur = 2
    while True:
        if sieve[cur]: # curの倍数は消す
            m = 2
            while cur * m <= max_prime:
                sieve[cur * m] = False
                m += 1
        
        cur += 1
        while not sieve[cur]:
            cur += 1

        if cur > math.sqrt(max_prime):
            break

    # x以上で素数のものを探す
    for i in range(x, max_prime + 1):
        if sieve[i]:
            print(i)
            return


if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
n = int(input())
for i in range(n, 100004):
    flag = 0
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            flag = 1
            break
    if flag == 0:
        print(i)
        break

Submission status: Accepted

Solution code:
n=int(input())
m=100003
L=[1]*(m+1)
L[0]=L[1]=0
for i in range(2,int(m**0.5)+1):
    if L[i]:
        for j in range(i*i,m+1,i):
            L[j]=0
for i in range(n,m+1):
    if L[i]==1:
        print(i)
        exit()

Submission status: Accepted

Solution code:
def solve():
    x = int(input())

    is_prime_list = [0 for i in range(10**6 + 1)]

    for i in range(2, len(is_prime_list)):
        if is_prime_list[i] == 0:
            is_prime_list[i] = 1
            
            for j in range(2 * i, len(is_prime_list), i):
                is_prime_list[j] = 2

    for _i in range(x, len(is_prime_list)):
        if is_prime_list[_i] == 1:
            print(_i)
            return


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
n=int(input())

prime = [True] * (2*n + 1)
prime[0] = False
prime[1] = False
for i in range(2, int(n**0.5) + 1):
	if not prime[i]:
		continue
	for j in range(i * 2, 2*n + 1, i):
		prime[j] = False
for i in range(2*n+1) :
	if prime[i]:
		if i>=n:
			print(i)
			break

Submission status: Accepted

Solution code:
import math

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

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

print(X)

Submission status: Accepted

Solution code:
import math
from sys import exit
X = int(input())

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

Submission status: Accepted

Solution code:
X = int(input())

def isprime(x):
  if x == 2:
    return True
  for i in range(2, x//2+1):
    if x % i == 0:
      return False
  return True

def minprime(x):
  while True:
    if isprime(x):
      return x
    x += 1

print(minprime(X))

Submission status: Accepted

Solution code:
def is_prime(n):
    if n<2:
        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:
def is_prime(n):
    if n<4:
        return True
    else:
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                return False
        return True

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

Submission status: Accepted

Solution code:
x = int(input())
prime = [2,3]
j = 3
while prime[-1] < 1000:
    j = j + 2
    i = 1
    pr = True
    while prime[i]*prime[i] <= j:
        if j % prime[i] == 0:
            pr = False
            break
        i = i+1
    if pr == True:
        prime.append(j)
        
newprime = 0
while newprime == 0:
    pr = True
    for i in range(len(prime)):
        if x == prime[i]:
            newprime = x
            break
        elif x %  prime[i] == 0:
            pr = False
            break
    if pr == True:
        newprime = x
    x = x+1
print(newprime)

Submission status: Accepted

Solution code:
import math

x = int(input())

primes = []

if x == 2:
    print(2)
    exit(0)

for n in range(3, 10000000000, 2):
    f = True
    mp = math.ceil(math.sqrt(n))
    for p in primes:
        if p > mp:
            break
        if n % p == 0:
            f = False
            break
    if f:
        primes.append(n)
        if n >= x:
            print(n)
            exit(0)

Submission status: Accepted

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

n = 10**6
s = int(math.sqrt(n)) + 1
p = [True]*(n+1)
p[0] = False
p[1] = False

for i in range(4, n+1, 2):
  p[i] = False
  
for i in range(3, s+1, 2):
  if p[i]:
    for j in range(i+i, n+1, i):
      p[j] = False
      
while True:
  if p[x] == True:
    print(x)
    break
  x += 1

Submission status: Accepted

Solution code:
X = int(input())

def isprime(x):
  for i in range(2, x//2+1):
    if x % i == 0:
      return False
  return True

def minp(x):
  res = x
  while True:
    if isprime(res):
      return res
    res += 1

print(minp(X))

Submission status: Accepted

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

n = int(input())
for i in range(n, 2 * 10 ** 5):
    if prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
import math
x = int(input())
if x == 2:
     print(2)
     sys.exit()
a = [i for i in range(2*x+1)]
for i in range(2,int(math.sqrt(2*x)) + 1):
     if a[i] != 0:
          for j in range(1,2*x // i + 1):
               a[i*j] = 0

for i in range(x):
     if a[x + i] != 0:
          print(a[x + i])
          break

Submission status: Accepted

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

x=int(input())
for i in range(x,10**6):
    if sosu(i)==True:
        print(i)
        break

Submission status: Accepted

Solution code:
from math import sqrt, floor
def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    for i in range(3, floor(sqrt(n))+1, 2):
        if n % i == 0: return False
    return True

val = (lambda x: x if x % 2 != 0 or x == 2 else x + 1)(int(input()))

for i in range(val, val * 2 + 1):
    if is_prime(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
X = int(input())

def prime_factorize(x):
    i = 2
    ans = []
    while i * i <= x:
        if x % i == 0:
            return False
        else:
            i += 1
    return True

while True:
    if prime_factorize(X) is True:
        print(X)
        exit()
    else:
        X += 1

Submission status: Accepted

Solution code:
x = int(input())
def isPrime(n):
	if n == 2 or n == 3:return True
	i = 2
	while i*i <= n:
		if n%i == 0:return False
		i += 1
	return True

for i in range(x,2*x):
	if isPrime(i):print(i);exit()
exit()

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    if n==2:
        print("2")
        exit()
    for j in range(10000):
        flag = 1
        a = int((n+j)**0.5)+1
        for i in range(2, a+1):
            if (n+j) % i== 0:
                flag = -1
            if i == a and flag ==1:
                print(n+j)
                exit()
resolve()

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    primel = [2]
    for i in range(3,331):
        k = 0
        for j in range(len(primel)):
            if i % primel[j] == 0:
                break
            else:
                k += 1
            if k == len(primel):
                primel.append(i)

    for i in range(0, 100000):
        k=0
        for j in range(len(primel)):
            if (n+i) == primel[j]:
                print(n + i)
                exit()
            if (n+i) % primel[j] == 0:
                break
            else:
                k += 1
            if k == len(primel):
                print(n + i)
                exit()
resolve()

Submission status: Accepted

Solution code:
X = 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
    return is_prime

is_prime = sieve(2*10**5)
p = X
while is_prime[p-1] == False:
  p+=1
print(p)

Submission status: Accepted

Solution code:
def is_prime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    if n % 2 == 0:
        return False

    for i in range(3, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

    return True

def solve():
    N = int(input())
    ans = 0
    for i in range(10**3):
        if is_prime(N+i):
            ans = N+i
            break
    return ans

print(solve())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

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 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 1:
    if is_prime(N) == True:
        print(N)
        exit()
    else:
        N += 1

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def primes(x):
    is_prime = [True] * (x + 1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, int(sqrt(x))+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, x+1, i):
            is_prime[j] = False

    return [i for i in range(x+1) if is_prime[i]]


def main():
    X = INT()

    lis = primes(100003)
    print(lis[bisect_left(lis, X)])


if __name__ == '__main__':
        main()

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X = INT()

def is_prime(n):
    if n == 1: return False

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

    return True

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

Submission status: Accepted

Solution code:
n=int(input()) 
while(1): 
	bool_1=True 
	for i in range(2,int(n**0.5//1)):   
		if n % i ==0:  
			bool_1=False 
			break     
	if bool_1:break 
	n+=1 
print(n)

Submission status: Accepted

Solution code:
n=int(input()) 
m=10**5+4 
for i in range(n,m): 
	lst=[] 
	if all(( i % j) !=0 for  j in range(2,int(n**0.5//1+1))): 
		print(i) 
		break

Submission status: Accepted

Solution code:
def sieve(n: int) -> set: #返り値はset
    if n < 2:
        return set()
    
    num = [True]*n
    num[0] = num[1] = False
    for i in range(3,int(n**0.5)+1,2):
        if num[i]:
            num[i * i:: 2 * i] = [False] * ((n - i ** 2 - 1) // (2 * i) + 1)
    return {2}|{i for i in range(3,n,2) if num[i]}

primelist = sieve(10**5+100)
l = [0]+list(sorted(primelist))
X = int(input())
for i in range(len(l)):
    if l[i]>=X:
        print(l[i])
        break

Submission status: Accepted

Solution code:
x = int(input())

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


def main():
	global x
	while not is_prime(x):
		x += 1

	print(x)

main()

Submission status: Accepted

Solution code:
x = int(input())
st = x
if x % 2 == 0:
  st = x + 1
div = 3
  
while div < st**0.5:
  if st % div == 0:
    st += 2
    div = 3
  else:
    div += 2
else:
  if x == 2:
    print(2)
  else:
    print(st)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X = int(input())
ok = 0
while(ok == 0):
    ok = 1
    for i in range(2,X):
        if(X%i==0):
            ok = 0
            break
    X += 1
print(X-1)

Submission status: Accepted

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

def callIsPrime(input_num):
    while True:
        if is_prime(input_num) == True:
            return input_num
        else:
            input_num += 1

print(callIsPrime(int(input())))

Submission status: Accepted

Solution code:
x = 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


sosu = False

while sosu==False:
    sosu = is_prime(x)
    x += 1

print(x-1)

Submission status: Accepted

Solution code:
import math
import sys

x = int(input())

for i in range(x, 100004):
    ans = True
    for k in range(2, int(math.sqrt(i)) + 1):
        if i % k == 0:
            ans = False
            break
    if ans == True:
        print(i)
        sys.exit()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

X = int(input())

for x in range(X, X*2):
    if is_prime(x):
        print(x)
        exit()

Submission status: Accepted

Solution code:
import math
X = int(input())
def is_prime(x):
  n = 2
  while n < int(math.sqrt(x)):
    if x % n == 0:
      return False
    n += 1
  return True
while not is_prime(X):
  X += 1
print(X)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left as bl

    def sosuu(n):
        p = [False]*2+[True]*(n-1)
        for i in range(2, int(n**0.5)+1):
            if not p[i]:
                continue
            for j in range(i*2, n+1, i):
                p[j] = False
        return [i for i in range(n+1) if p[i]]

    x = int(input())
    y = sosuu(100010)
    print(y[bl(y, x)])


main()

Submission status: Accepted

Solution code:
X = int(input())

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

for i in range(X,110000):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
X=int(input())
while any(X%i==0 for i in range(2,X)):X+=1
print(X)

Submission status: Accepted

Solution code:
from math import sqrt
from bisect import bisect_left


def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of primes
    """

    primes = []
    li = list(range(2, x + 1))

    while li[0] <= sqrt(x):
        p = li[0]
        primes.append(p)
        li = [e for e in li if e % p != 0]

    primes += li
    return primes


x = int(input())

primes = sieve(10 ** 6)

i = bisect_left(primes, x)
ans = primes[i]
print(ans)

Submission status: Accepted

Solution code:
x = int(input())
for i in range(x, x+10**5):
    for j in range(2, int(x**0.5)+1):
        if i%j == 0:
            break
    else:
        print(i)
        break

Submission status: Accepted

Solution code:
import math
X = int(input())
def is_prime(x):
  n = 2
  while n <= math.sqrt(x):
    if x % n == 0:
      return False
    n += 1
  return True
while not is_prime(X):
  X += 1
print(X)

Submission status: Accepted

Solution code:
N = int(input())

M = N -1
flg = 0
while flg == 0:
  M += 1
  flg = 1
  for n in range(2,M-1):
    if M%n == 0:
      flg = 0
      break

print(M)

Submission status: Accepted

Solution code:
X = 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
  
for i in range(X, 10 ** 7):
  if is_prime(i):
    print(i)
    break

Submission status: Accepted

Solution code:
from math import sqrt

x = int(input()) - 1
if x in (1, 2):
    print(x+1)
    exit()

while True:
    x += 1
    
    if x % 6 != 1 and x % 6 != 5:
        continue
    
    x_sqrt = int(sqrt(x))
    if x % 2 != 0:
        for a in range(3, x_sqrt+1, 2):
            if x % a == 0:
                break
        else:
            print(x)
            break
    else:
        continue