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 sys
from collections import deque
#import numpy as np
import math
#sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def solve():
    exclude = set()
    prime = set()
    for i in range(2,int(math.sqrt(x))+1):
        if i in exclude:
            continue
        prime.add(i)
        j = i
        while j<=x+2*i:
            exclude.add(j)
            j += i
    current = x
    while True:
        for rep in prime:
            if current%rep==0:
                break
        else:
            print(current)
            return
        current += 1
    return

if __name__=='__main__':
    x = I()
    solve()

Submission status: Accepted

Solution code:
import math

def prime(n):
    if n==1:
        return False
    if n==2:
        return True
    if n%2==0:
        return False
    for i in range(3,math.ceil(n**0.5)+1,2):
        if n%i==0:
            return False
    
    return True

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x = int(input())
ans = x
while True:
  jud = 0
  if(ans <= 2):
    print(2)
    break
  if(ans%2==0):
    jud += 1
  i = 3
  while i < ans**(1/2):
    if(jud>0):
      break
    if(ans%i == 0):
      jud += 1
    i += 2
  if(jud==0):
    print(ans)
    break
  ans += 1

Submission status: Accepted

Solution code:
import bisect, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    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] = False
    return [i for i in range(n+1) if is_prime[i]]

def resolve():
    X = I()

    primes = sieve(X * 2)
    idx = bisect.bisect_left(primes, X)
    print(primes[idx])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]

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

Submission status: Accepted

Solution code:
#21 Next Prime
X=int(input())
num=X 
for _ in range(1000000):
    flg = True
    # 2からnumまでの数でわりきれるかどうか（True：どの数字でも割り切れなかったので、素数。False:素数じゃない）
    for i in range(2,num):
        if num%i==0:
            flg = False
            break
    
    if flg:
        print(num)
        break
    else:
        num+=1
        pass

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

import math

# Mまでの素数全列挙(エラトステネスの篩)
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#print(data)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n=int(input())

def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  if n % 2 == 0:
    # ２ではない偶数は素数ではない
    return False
  
  # nの半分まで計算する範囲を絞る
  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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
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))  # type: int
    print(f'{solve(X)}')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# input = sys.stdin.readline
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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def is_prime(x):
    a = int(math.sqrt(X)) + 1#ある数が素数かどうかはO(√A)で判定できる
    for i in range(2,a):
        if x % i == 0:
            return False
    return True#xは素数

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def make_prime_checker(n):
    # nまでの自然数が素数かどうかを表すリストを返す  O(nloglogn)
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#print(sosu[x])
while sosu[x]==0:
    x += 1
print(x)

Submission status: Accepted

Solution code:
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
    #print(x)
    x+=2

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(X)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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