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

Solution (Python):
x=int(input())
if x <4:
  print(x);exit()
while 1:
  for i in range(2,int(x**.5)+1):
    if x%i:continue
    break
  else:print(x);exit()
  x+=1

Solution (Python):
def erathosthenes(n):
    if n < 2:
        return False
    
    prime_list = []
    search_max = n ** 0.5

    cand = [i for i in range(2, n+1)]
    while True:
        prime_cand = cand[0]
        if search_max <= prime_cand:
            return prime_list + cand
        prime_list.append(prime_cand)
        cand = [j for j in cand if j % prime_cand != 0]

X = int(input())
SIZE = 100003
prime_list = erathosthenes(SIZE)

for i in range(len(prime_list)):
    if prime_list[i] >= X:
        print(prime_list[i])
        break

Solution (Python):








x = int(input())

def sosu(x):
    for i in range(2, x):
        if (x % i == 0):
            return False
    return True

for i in range(x, 100000+5):
    if (sosu(i)):
        print(i)
        exit()

Solution (Python):

X=int(input())
num=X 
for _ in range(1000000):
    flg = True
    
    for i in range(2,num):
        if num%i==0:
            flg = False
            break
    
    if flg:
        print(num)
        break
    else:
        num+=1
        pass

Solution (Python):
import math

X = int(input())

def prime(num):
    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False

    m = math.floor(num/2) + 1
    for p in range(3, m, 2):
        if num % p == 0:
            return False
    return True

while prime(X) == False:
    X += 1

print(X)

Solution (Python):
X=int(input())
n=100004
L=[True]*n
L[0]=False
L[1]=False
for i in range(2,int(n**0.5)+1):
  if L[i]:
    for j in range(i*2,n):
      if j%i==0:
        L[j]=False
for i in range(X,n):
  if L[i]==True:
    print(i)
    exit()

Solution (Python):
N = int(input())

import math


def primes(M):
    is_prime = [-1 for _ in range(M+1)]
    for m in range(2, M+1):
        if is_prime[m] == -1:
            is_prime[m] = 1
            l = 2
            while m*l <= M:
                is_prime[m*l] = 0
                l += 1
    primes = []
    for p in range(2, M+1):
        if is_prime[p] == 1:
            primes.append(p)
    return primes


P = primes(2*N)
ans = -1
for p in P:
    if p >= N:
        ans = p
        break
print(ans)

Solution (Python):
X=int(input())
i=2
while i < X:
    if X % i == 0:
        X += 1
        i = 2
    else:
        i += 1
print(X)

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

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]

data = get_sieve_of_eratosthenes(x*2)
for i in data:
  if i>=x:
    print(i)
    break

Solution (Python):
x = int(input())

eratostenes = [True] * 10**6
for i in range(2, len(eratostenes)):
    if eratostenes[i]:
        for j in range(i * 2, len(eratostenes), i):
            eratostenes[j] = False
for i in range(x, len(eratostenes)):
    if eratostenes[i]:
        print(i)
        exit()

Solution (Python):
import math

n=int(input())

def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  if n % 2 == 0:
    
    return False
  
  
  m = math.floor(n / 2) + 1
  for p in range(3, m, 2): 
      if n % p == 0:
        return False
  return True

while isPrime(n)==False:
  n+=1

print(n)

Solution (Python):
x=int(input())

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

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

while True:
    
    k=1

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

        k+=1
    
    x+=2

Solution (Python):
x = int(input())
while True:
    i = 2
    prime = True
    while i * i <= x:
        if x % i == 0:
            prime = False
            break
        i += 1
    if prime:
        print(x)
        quit()
    x += 1

Solution (Python):
import math
x=int(input())
def eratosthenes(n):
    """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]
ans=eratosthenes(10**5+3)
for i in  range(len(ans)):
    if ans[i]>=x:
        print(ans[i])
        exit()
    else:
        pass

Solution (Python):
def prime_list():
  p_lis = [True] * (2 * 10**5 + 1)
  p_lis[0], p_lis[1] = False, False
  for i in range(2, 2 * 10**5 + 1):
    if p_lis[i]:
      j = 2
      while j * i <= 2 * 10**5:
        p_lis[j*i] = False
        j += 1
  return p_lis

x = int(input())
p_lis = prime_list()
j = 0
while True:
  if p_lis[x+j]:
    print(x+j)
    break
  j += 1

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

for i in range(X,2*X):
    for j in range(2,i):
        if i % j == 0:
            break
        if j == i-1:
          print(i)
          exit()

Solution (Python):
import sys
import numpy as np
import numba
from numba import jit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

s = int(input())

@jit
def main(s):
  while True:
    flag = False
    for i in range(2, int(s**(1/2)+1)):
      if s%i == 0:
        flag = True
    if not flag:
      return s
    s += 1
print(main(s))

Solution (Python):


from typing import *
import collections
import functools
import itertools
import math
import sys

INF = float('inf')


def prime(min=1, max=float('inf')):
    primes = [2]
    if min <= 2 < max:
        yield 2

    def odd(min=1, max=float('inf')):
        counter = min + (min % 2 == 0)
        while counter < max:
            yield counter
            counter += 2

    if max != float('inf'):
        numbers = list(odd(3, max))
        for i in range(len(numbers)):
            if numbers[i] != 0:
                if min <= numbers[i]:
                    yield numbers[i]

                o = odd(3)
                while True:
                    index = numbers[i] * next(o) // 2 - 1
                    if index >= len(numbers):
                        break
                    numbers[index] = 0

    else:
        for o in odd(3, max):
            for p in primes:
                if o % p == 0:
                    break
            else:
                primes.append(o)
                if min <= o:
                    yield o
                if max < o:
                    break


def solve(X: int):
    return next(prime(X, int(1e5) + 5))


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  
    print(f'{solve(X)}')


if __name__ == '__main__':
    main()

Solution (Python):
x = int(input())
prlist = []
n = 2
sosuu = 0
answer = 0
while n**2 < x:
    for i in prlist:
        if n % i == 0:
            sosuu = 1
            break
    if sosuu == 0:
        prlist.append(n)
    sosuu = 0
    n += 1
sosuu = 1
while answer == 0:
    for j in prlist:
        if x % j == 0:
            sosuu = 2
            break
    if sosuu == 1:
        answer = x
    sosuu = 1
    x += 1
print(answer)

Solution (Python):
X=int(input())
ans=0
for i in range(X,10**5+100):
    cond=True
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            cond=False
            break
    if cond:
        ans=i
        break

print(ans)

Solution (Python):
num = 0
x = int(input())
while num != 1:
    num = 0
    for i in range(2,x+1):
        if x%i == 0:
            num += 1
    j = x
    x += 1
print(j)

Solution (Python):
def crivo(n):
    primos = [True] * n
    primos[0] = primos[1] = False

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

def main():
    primos = crivo(100004)
    x = int(input())
    for i in range(x, 100004):
        if primos[i]:
            print(i)
            break

main()

Solution (Python):
from math import sqrt, ceil
X = int(input())

def isprime(x):
    if x <= 1:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False

    for j in range(3, ceil(sqrt(x))+1, 2):
        if x % j == 0:
            return False
    return True

for i in range(10**9):
    if isprime(X+i):
        print(X+i)
        break

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

count = 0
if X % 2 == 0:
  X += 1
while True:
  now = X + count
  k = 3
  while k*k <= now:
    if now % k == 0:
      count += 2
      break
    else:
      k += 2
      continue
  if k*k > now:
    break
  
  
print(now)

Solution (Python):
x = int(input())
A = [0]*(2*10**5)
for i in range(2,len(A)):
    if A[i]==0:
        for j in range(2*i,len(A),i):
            A[j]=1
for i in range(x,len(A)):
    if A[i]==0:
        print(i);exit()

Solution (Python):
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

X = int(input())
for i in range(X,99992):
    if len(make_divisors(i)) == 2:
        print(i)
        break
else:
    print(100003)

Solution (Python):
X=int(input())
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
while len(prime_factorize(X))!=1:
    X+=1
print(X)

Solution (Python):
num = 0
x = int(input())
while num != 1:
    num = 0
    for i in range(2,x+1):
        if x%i == 0:
            num += 1
    j = x
    x += 1
print(j)

Solution (Python):
X = int(input())
for i in range(X, 2*X):
    for j in range(2, X):
        if i%j==0:
            break
    else:
        print(i)
        break

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


def make_is_prime(N):
    prime = [1 for i in range(N+1)]
    prime[0] = prime[1] = 0
    for i in range(2,N+1):
        if prime[i] == 0: continue
        j = i**2
        while (j <= N):
            prime[j] = 0
            j += i
    return prime

a = make_is_prime(10**5+5)

N = int(input())

for i in range(N,10**5+5):
    if a[i] == 1:
        print(i)
        sys.exit()

Solution (Python):
def prime_list(num):
    list = [0]*2 + [1]*(num - 1)
    prime_list = []
    for i in range(2,num + 1):
        if list[i] == 1:
            for j in range(2, num//i + 1):
                list[i*j] = 0
    for i in range(num + 1):
        if list[i] == 1:
            prime_list.append(i)
    return prime_list

x = int(input())
prime = prime_list(100003)

while x not in prime:
    x += 1

print(x)

Solution (Python):
x = int(input())


def isPrime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = int(n**0.5)+1
    for p in range(3, m, 2):
        if n % p == 0:
            return False
    return True


while not isPrime(x):
    x += 1
print(x)

Solution (Python):
x = int(input())


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


for i in range(x, x+100):
    l = prime_factorize(i)
    if i in l:
        l.remove(i)
    if not l:
        print(i)
        exit()

Solution (Python):
from math import *
n=int(input())
f=0
for i in range(n,100009):
    c=0
    for j in range(1,i+1):
        if(i%j==0):
            c=c+1
        if(c>=3):
            break
    if(c==2):
        print(i)
        f=1
        exit()

Solution (Python):
def main():
    x = int(input())
    for i in range(x, 110000):
        count = 0
        for j in range(1, i+1):
            if i % j == 0: count += 1
            if count > 3: continue
        if count == 2: return i


print(main())

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

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

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

Solution (Python):
x = int(input())
def sosuu(n):
    jud = 0
    for k in range(2,int(n**(0.5))):
        if n % k == 0:
            jud = 1
    if jud == 0:
        return True
    else:
        return False

for i in range(x,100004):
    if sosuu(i):
        print(i)
        break

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

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

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

x = inp()
serach_number = 100003
 
def sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []
 
    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)
 
        i = 0
        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1
    return prime_list

data = sieve_of_eratosthenes(serach_number)

for i in data:
    if i >= x:
        print(i)
        break

Solution (Python):
def is_prime(n):
  if n == 1:
    return True
  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)==True:
    break
  x+=1
print(x)

Solution (Python):
x = int(input())

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

X = int(input())
double = X*10+1
s = set()
for i in range(2, double):
    if i in s:
        continue
    if i>=X:
        print(i)
        break
    cnt = 1
    while cnt*i<=double:
        s.add(i*cnt)
        cnt += 1

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

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

Solution (Python):
X = int(input())
j = 2
for i in range(X,(X - 1) * 2):
  while i % j != 0 and j <= i:
    j += 1
  if j == i:
    print(i)
    break
  j = 2
if X == 2:
  print(2)

Solution (Python):
def 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())
for i in range(x,x+1000000):
    if len(factorize(i))==1:
        print(i)
        exit()

Solution (Python):
n = int(input())
while 1:
    for i in range(2, int(n**0.5)+1):
        if n % i < 1:
            break
    else:
        print(n)
        break
    n += 1

Solution (Python):
x=int(input())

while True:

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

Solution (Python):
X = int(input())

for i in range(X, 10**6):
    for n in range(2, int(i**0.5)+1):
        if i % n == 0:
            break
    else:
        print(i)
        break

Solution (Python):
import math

prime = [2]
for i in range(3, int(math.sqrt(200000)), 2):
  for j in prime:
    if i % j == 0:
      break
    elif math.sqrt(i) < j:
      prime.append(i)
      break

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

cand = 0
while not cand:
  for p in prime:
    if X != 2 and X % p == 0:
      break
    elif math.sqrt(X) < p:
      cand = X
      break
  X += 2

print(cand)

Solution (Python):
import math
a = int(input())
b = int(math.sqrt(a)) +1

for k in range(200000):
    count = 0
    for i in range(2,b):
        if (a+k) % i == 0:
            count +=1
    if count == 0:
        print(a+k)
        break

Solution (Python):
import sys

n=int(input())
c=False


for i in range(n,100000000):
  c=False
  
  for j in range(2,i):
    if i%j==0:
      c=True
      continue
     
  if c==True:
    continue
    
  else:
    print(i)
    sys.exit()

Solution (Python):
N = int(input())

def prime_check(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

for x in range(N, 1000000):
    if prime_check(x):
        print(x)
        exit()

Solution (Python):
x = int(input())
a = x
while True:
    isPrime = True
    for i in range(2, x-1):
        if x % i == 0:
            isPrime = False
            break
    if isPrime:
        break
    x += 1
print(x)

Solution (Python):
X = int(input())

prime = []
for n in range(3, X, 2):
    lim = int(n ** 0.5)
    f = True
    for p in prime:
        if p > lim:
            break
        if n % p == 0:
            f = False
            break
    if f:
        prime.append(n)
if X >= 3:
    prime = [2] + prime

for n in range(X, X+10**5):
    for p in prime:
        if n % p == 0:
            break
    else:
        print(n)
        break

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

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

for j in range(X,10**5+4):
    if is_prime(j):
        ans = j    
        break
print(ans)

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

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

for j in range(X,X+100):
    if is_prime(j):
        ans = j    
        break
print(ans)

Solution (Python):
x = int(input())
n = 10 * x
primes = [True] * n
for i in range(2, n):
    if primes[i]:
        for j in range(i * i, n, i):
            primes[j] = False

for i in range(x, n):
    if primes[i]:
        print(i)
        exit()

Solution (Python):
x = int(input())
n = 10 * x
primes = [True] * n
for i in range(2, n):
    if primes[i]:
        for j in range(i * i, n, i):
            primes[j] = False

for i in range(x, n):
    if primes[i]:
        print(i)
        exit()

Solution (Python):
def make_prime_checker(n):
    
    is_prime = [False, True, False, False, False, True] * (n//6+1)
    del is_prime[n+1:]
    is_prime[1:4] = False, True, True
    for i in range(5, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * (n//i-i+1)
    return is_prime

P = make_prime_checker(101010)
X = int(input())
for i in range(X, 101010):
    if P[i]:
        print(i)
        exit()

Solution (Python):
def main():
    N = int(input())
    ans = 0

    if N == 2:
        print(2)
        return
    
    while True:
        flg = True
        for i in range(2, ((N + 1) // 2) + 1):
            if N % i == 0:
                flg = False
                break
        
        if flg:
            break
        else:
            N += 1
    
    print(N)

if __name__ == '__main__':
    main()

Solution (Python):
import math
X = int(input())
X -= 1

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

Solution (Python):
X = int(input())
while True:
    prime = True
    for i in range(2, int(X**0.5)+1):
        if X % i == 0:
            prime = False
            break
    if prime:
        print(X)
        exit()
    X += 1

Solution (Python):
x = int(input())

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

i = x
while True:
    if judge(i):
        print(i)
        break
    i += 1

Solution (Python):
X = int(input())
ans = 0
import math
while True:
	for x in range(2, int(math.sqrt(X)) + 1):
		if X % x == 0:
			break
	else:
		print(X)
		break
	X += 1

Solution (Python):
x = int(input())

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

Solution (Python):
m = 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 is_prime(m) is False:
    m += 1
    
print(m)

Solution (Python):
x=int(input())
def eratosthenes(n):
  l0=list(range(2,n+1))
  l1=[1]*(n+1)
  l1[0]=0
  l1[1]=0
  for li in l0:
    if li>int(n**0.5):
      break
    if l1[li]==1:
      k=2
      while k*li<=n:
        l1[k*li]=0
        k+=1
  ret=[i for i,li in enumerate(l1) if li==1]
  return ret
a=eratosthenes(x)
if x in a:
  print(x)
  exit()
while True:
  flg=True
  for ai in a:
    if x%ai==0:
      flg=False
      break
  if flg:
    print(x)
    exit()
  x+=1

Solution (Python):
x = int(input())
sosu = [int(i) for i in range(2*x)]
sosu[1] = 0
for i in range(2,x):
    if sosu[i]!=0:
        j = 2
        while i * j < 2*x:
            sosu[i*j]=0
            j += 1

while sosu[x]==0:
    x += 1
print(x)

Solution (Python):
def cP(x):
    if x%2==0 or x%3==0 or x%5==0 :
        return 0
    for i in range(7,int(x**0.5+1),2):
        if x%i==0:
            return 0
    return 1


x = int(input())
if x==2 or x==3 or x==5 :
    print(x)
    exit()

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

while 1:
    if cP(x) :
        break
    
    x+=2

print(x)

Solution (Python):
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:
    p = prime_factorize(x)
    if len(p) == 1:
        print(p[0])
        break
    x += 1

Solution (Python):
import math


def resolve():
    import sys
    input = sys.stdin.readline
    
    
    x = int(input().rstrip())

    def get_sieve_of_eratosthenes(n: int):
        candidate = [i for i in range(2, n + 1)]

        primes = []
        while len(candidate) > 0:
            prime = candidate[0]
            candidate = [num for num in candidate if num % prime != 0]
            primes.append(prime)
        return primes

    
    primes = get_sieve_of_eratosthenes(x)

    ans = x
    if not x in primes:
        while True:
            if any([ans % prime == 0 for prime in primes]):
                ans += 1
                continue
            break

    print(ans)




if __name__ == "__main__":
    resolve()

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

Solution (Python):
X = int(input())
res = X
j = 0
Flags = []
flg = True
for i in range(2,X+1):
  j = i+i
  flg = True
  while flg:
    Flags.append(j)
    if j > X:
      flg = False
    j += i
while res in Flags:
  res += 1
print(res)

Solution (Python):
X = int(input())
n = 2

while n<X:
  if X%n==0:
    X+=1
    n=2
  else:
    n+=1

print(X)

Solution (Python):
X = int(input())
if X <= 2:
    print(2)
    exit()
S = [2]
for i in range(3, 10**6, 2):
    f = True
    for s in S:
        if s > i**(0.5): break
        if i % s == 0:
            f = False
            break
    if f:
        S.append(i)
        if i >= X:
            print(i)
            break

Solution (Python):
import math
import sys
input = sys.stdin.readline

def isPrime(n):
    i = 2
    flag = True
    while i * i <= n:
        if n % i == 0:
            flag = False
            break
        else:
            i += 1
    return flag


x = int(input())

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

Solution (Python):
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
    X+=1
    
print(X)

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

Solution (Python):
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    def isPrime(n):
        if n == 2:
            return True
        if n%2 == 0:
            return False
        m = math.floor(math.sqrt(n))+1
        for p in range(3,m,2):
            if n%p == 0:
                return False
        return True

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

if __name__=="__main__":
    main()

Solution (Python):
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    x = int(input())
    while True:
        if all( x%i != 0 for i in range(2,x)):
            print(x)
            exit()
        x += 1

if __name__=="__main__":
    main()

Solution (Python):
import math
s=int(input())
def sosuuukana(x):
    y=int(math.sqrt(x))
    f=0
    for i in range(2,y+1):
        if x%i==0:
            f=f+1
            break
    return f
while sosuuukana(s)>0:
    s=s+1
else:
    print(s)

Solution (Python):
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,10**7):
    if is_prime(i):
        print(i)
        exit()

Solution (Python):
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:
  prime = int(math.sqrt(X))
  if is_prime(X):
    break
  X += 1
print(X)

Solution (Python):
import sys
import math


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instr = lambda: sys.stdin.readline()
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

x = inint()

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


for i in range(1,10**6):
    bool = isPrime(i)
    if bool and i >= x:
        print(i)
        break

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

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

    while not is_prime(x):
        x += 1
    print(x)

solve()

Solution (Python):
def solve():
    from bisect import bisect_right, bisect, bisect_left
    x = int(input())
    n = 100100
    primes = set(range(2, n + 1))
    for i in range(2, int(n ** 0.5 + 1)):
        if i not in primes:
            i += 1
        else:
            ran = range(i * 2, n + 1, i)
            primes.difference_update(ran)
    primes = list(primes)
    y = bisect_left(primes, x)
    print(primes[y])
    
    
solve()

Solution (Python):
N= int(input())
a = [0]*110000
if N == 2:
  print(2)
else:
  for i in range(2,N):
    k = i
    j = 2
    while k<110000:
      a[k]+=1
      k = int((k/(j-1))*j)
      j+=1
  
  for i in range(N,110001):
    if a[i]>0:
      continue
    elif a[i]==0:
      print(i)
      break

Solution (Python):
X = int(input())

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

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

Solution (Python):
X = int(input())

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

Solution (Python):
X=int(input())
while True:
    flg = True
    for i in range(2,int(X**1/2)+1):
        if X%i == 0:
            flg = False
            break
    if flg == True:
        print(X)
        break
    else:
        X += 1

Solution (Python):
X = int(input())

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

Solution (Python):
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve

X = int(input())

N = 10 ** 6
prime_table = make_prime_table(N)
for i in range(X, N + 1):
    if prime_table[i] == i:
        print(i)
        break

Solution (Python):

x=int(input())
p=[1 for i in range(100010)]
for i in range(2,100011):
    k=2*i
    while k<=100009:
        p[k]=0
        k+=i
z=x
f=0
while f==0:
    if p[z]==1:
        print(z)
        f=1
    z+=1