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

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

n = X
while not is_prime(n):
    n += 1
print(n)

Submission status: Accepted

Solution code:
def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)] 
    i=0
    p = pl[0]
    while p**2<=n:
        pl = [pl[j] for j in range(len(pl)) if pl[j]%p!=0 or j<=i]
        i+=1
        p=pl[i]
    return pl

pl = sieve_of_eratosthenes(10**6)

X = int(input())

for p in pl:
    if p>=X:
        print(p)
        break

Submission status: Accepted

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n = INT()

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

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

    return True

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

Submission status: Accepted

Solution code:
import math
def eratos(n):
    isprime = [True for i in range(n+1)]
    isprime[0] = False
    isprime[1] = False
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i]:
            j = i + i
        while j <= n:
            isprime[j] = False
            j = j + i
    return isprime        

if __name__ == "__main__":
    maxn = 10**5+13
    x = int(input())
    ans = 0
    isprime = eratos(maxn)
    for i in range(x, maxn):
        if isprime[i]:
            ans = i
            break
    print(ans)

Submission status: Accepted

Solution code:
x = int(input())

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

for i in range(x, 10**18):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


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


def main():
    # A, B, K = get_inputs(int)
    # if A >= K:
    #     print(A-K, B)
    # elif A + B >= K:
    #     print(0, B - (K-A))
    # else:
    #     print(0, 0)
    X = get_input(int)
    n = X
    while True:
        if is_prime(n):
            print(n)
            return
        else:
            n += 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def primes(n):
  is_prime=[True]*(n+1)
  is_prime[0]=False
  is_prime[1]=False
  for i in range(2,int(n**0.5)+1):
    if not is_prime[i]:
      continue
    for j in range(i*2,n+1,i):
      is_prime[j]=False
  return [i for i in range(n+1) if is_prime[i]]

l=primes(100010)
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())

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

Submission status: Accepted

Solution code:
def examA():
    S, T = LSI()
    ans = T+S
    print(ans)
    return

def examB():
    A, B, K = LI()
    if A>K:
        A -=K
        print(A,B)
        return
    if A+B>K:
        B -=(K-A)
        A = 0
        print(A,B)
        return
    A = 0; B = 0
    print(A,B)
    return

def examC():
    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 = I()
    while(True):
        if is_prime(X):
            ans = X
            break
        X +=1
    print(ans)
    return

def examD():
    return

def examE():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
import sys

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


def solve():
    X = int(input())
    for i in range(100000):
        if is_prime(X + i):
            print(X + i)
            break

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
X = int(input())

def is_prime(x):
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

while not is_prime(X):
    X += 1

print(X)

Submission status: Accepted

Solution code:
X = int(input())

import math

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

for x in range(X, 10**6):
    if isPrime(x):
        print(x)
        exit()

Submission status: Accepted

Solution code:
from math import sqrt
M = 10**6
p = [1]*(M+1)
p[0] = p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

x = int(input())

for i in range(M):
   if p[x+i] == 1:
      print(x+i)
      import sys
      sys.exit()

Submission status: Accepted

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
X = int(input())


def is_prime(n): 
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True

for x in range(X, 10**6):
    if is_prime(x):
        print(x)
        break

Submission status: Accepted

Solution code:
import sys
from math import floor, sqrt
from bisect import bisect_left as bi_l

def prime_nums(n):
    sieve = set(range(2, n + 1))
    non_prime = set(range(2 * 2, n + 1, 2))
    sieve -= non_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            non_prime = set(range(i * 2, n + 1, i))
            sieve -= non_prime
    return sieve

ps = prime_nums(10 ** 6)
ps = sorted(ps)

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

def main():
    return ps[bi_l(ps, x)]

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:


# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def Eratosthenes(N): #N以下の素数のリストを返す
    #iが素数のときis_prime_list[i]=1，それ以外は0
    N+=1
    is_prime_list = [True]*N
#    is_prime_list[0], is_prime_list[1] = False, False #リストが必要なときはこの2行を有効化
#    for j in range(4,N,2): is_prime_list[j] = False
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_list[i]:
            is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_list[i]]
#    return is_prime_list


N = int(input())
a = Eratosthenes(2*N)

from bisect import bisect_left

print(a[bisect_left(a,N)])

"""
a,b,k = [int(i) for i in readline().split()]


if a >= k: a -= k
else:
    k -= a
    a = 0
    b = max(0,b-k)


print(*[a,b])
"""

Submission status: Accepted

Solution code:
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime
p = eratosthenes(100003)
X = int(input())
for n in p:
    if X<=n:
        break
print(n)

Submission status: Accepted

Solution code:
X = int(input())

L = [0]*10**6
i = 2
while i < 10**6:
    if L[i] != 0:
        i += 1
        continue
    L[i] = 1
    j = 2
    while i*j < 10**6:
        L[i*j] = -1
        j += 1
    i += 1
    
for i in range(X, 10**6):
    if L[i] == 1:
        print(i)
        break

Submission status: Accepted

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

ps = primes(2*10**5)

for p in ps:
    if p >= X:
        print(p)
        break

Submission status: Accepted

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


for j in range(10000):
    x = X+j
    xn = math.ceil(math.sqrt(x))
    flag = 0
    for i in range(xn-2):
        I = i+2
        if x%I == 0:
            flag = 1
            break
    if flag == 0:
        print(x)
        break

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


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

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


x = ri()

sieve = eratosthenes(10**6)
for i in range(x, 10**6):
    if sieve[i]:
        print(i)
        exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x = int(input())


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


for num in range(x, 10**7):
    if is_prime(num):
        print(num)
        exit()

Submission status: Accepted

Solution code:
def prime_list(n):
    # n以下の自然数で素数か否かのリストを作成
    ans = [True for _ in range(n+1)]
    ans[0] = False
    ans[1] = False
    for i in range(2,n+1):
        if ans[i]:
            for j in range(2*i,n+1,i):
                ans[j] = False
    return ans

x = int(input())
d = prime_list(2*x+1)
for i in range(x,len(d)):
    if d[i]:
        print(i)
        exit()

Submission status: Accepted

Solution code:
x = int(input())

def dec(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

for i in range(x,10**5+4):
    if len(dec(i)) == 1:
        print(i)
        exit()

print('error')

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
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

for i in range(n,n+10**6):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
from bisect import bisect_left

X = int(input())


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


p = sieve_of_eratosthenes(2 * 10 ** 5)

print(p[bisect_left(p, X)])

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

X = int(input())

for i in range(X, 10**6):
    if is_prime(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
X = int(input())

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

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
x=int(input())
t=2*(10**5)
p=[]
q=[1]*(t)
for i in range(2,t):
    if q[i]:
        p.append(i)
        for j in range(2*i,t,i):
            q[j]=0
print(p[bl(p,x)])

Submission status: Accepted

Solution code:
from math import sqrt
X = int(input())
def is_prime(n):
    for i in range(2,int(sqrt(n))+1):
        if n%i==0:return False
    return True
for i in range(X,10000000):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
import math

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

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

    return True
x=int(input())
for i in range(x,5*x):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
def isPrime(n):
    div = 2
    while div * div <= n:
        if n % div == 0: return False
        div += 1
    return True

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

Submission status: Accepted

Solution code:
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def isPrime(N):
    if N <= 1: return False
    return sum(primeFactor(N).values()) == 1

def findPrime(N):
    if N < 0: return -1
    i = N
    while True:
        if isPrime(i):
            return i
        i += 1

N = int(input())
print(findPrime(N))

Submission status: Accepted

Solution code:
n = int(input())
"""素因数分解"""
def factrize(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            #もし素因数を重複させたくないならここを加えてfct.append(b)を消す
            """
            if not b in fct:
                fct.append(b)
            """
            fct.append(b)
        b = b+1
    if n > 1:
        fct.append(n)
    return len(fct) == 1 #TFが帰る


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

Submission status: Accepted

Solution code:
X=int(input())
N=2*X
L=[1 for i in range(N)]
L[0]=0
L[1]=0
for i in range(2,N):
    if L[i]==1:
        for j in range(2*i,N,i):
            L[j]=0
M=X
while(1):
    if L[M]==1:
        print(M)
        break
    M+=1

Submission status: Accepted

Solution code:
# is a prime
def ispr(n):
    if n==1:
        return False
    elif n==2:
        return True
    elif n%2==0:
        return False
    else:
        k=3
        while k**2<=n:
            if n%k==0:
                return False
            else:
                k+=2
        return True

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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


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

Submission status: Accepted

Solution code:
X = input()

while True:
  t = X
  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())
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
n = X
while True:
    if is_prime(n):
        break
    n+=1
print(n)

Submission status: Accepted

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


def is_prime(n):
    # 1は素数ではない
    if n == 1:
        return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


for i in range(x, 10 ** 6):
    if is_prime(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
def eratosthenes(n: int) -> list:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, n // 2 + 1):
        if is_prime[i]:
            for j in range(2, n // i + 1):
                is_prime[i * j] = False
    return is_prime


x = int(input())
is_prime = eratosthenes(x * 2 + 100)
ans = x
while not is_prime[ans]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

def main():
    x = I()
    pr = Prime(10**11)
    while not pr.is_prime(x):
        x += 1

    return x


print(main())

Submission status: Accepted

Solution code:
def factorization(n):
    p=2
    fcr=[]
    while p*p<=n:
        while n%p==0:
            fcr.append(p)
            n//=p
        p+=1
    if n>1:
        fcr.append(n)
    return fcr

x=int(input())
while True:
 l=factorization(x)
 if len(l)==1:
  print(x)
  exit()
 else:
  x+=1

Submission status: Accepted

Solution code:
def prime_table(n):
    prime = [True]*(n+1)
    prime[0]=prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not prime[i]:
            continue
        for j in range(2*i, n+1, i):
            prime[j] = False
    return prime

m = 10**6
x = int(input())
table = prime_table(m)
for i in range(x, m+1):
    if table[i]:
        print(i)
        exit()

Submission status: Accepted

Solution code:
X = int(input())
def is_prime(n):
    if n == 2: return True
    if n < 2 or n%2 == 0: return False
    m = 3
    while m*m <= n:
        if n%m == 0: return False
        m += 2
    return True

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

Submission status: Accepted

Solution code:
x = int(input())

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

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

Submission status: Accepted

Solution code:
import math
def primes(x):
    x+=1
    if x < 2:
        return []

    prime = [i for i in range(x)]
    prime[1] = 0

    for p in prime:
        if p > math.sqrt(x):
            break
        if p == 0:
            continue
        for non_prime in range(2 * p, x, p):
            prime[non_prime] = 0

    return [p for p in prime if p != 0]


x = int(input())

p = primes(10**6)

for y in p:
    if x<=y:
        print(y)
        exit()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

# 素因数分解
def prime_factorization(n):
    fact=[]
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            fact.append(i)
    return fact
def main():
    X=I()
    while True:
        if not(prime_factorization(X)):
            print(X)
            return 
        X+=1

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def eratosthenes_sieve(n):
    if n < 2:
        return []

    is_primes = [True] * (n + 1)
    for x in range(2, int(n ** 0.5 + 1) + 1):
        if is_primes[x]:
            for mx in range(2 * x, n + 1, x):
                is_primes[mx] = False

    return [i for i in range(2, n + 1) if is_primes[i]]


X = int(input())
Primes = eratosthenes_sieve(10 ** 6)
for p in Primes:
    if p >= X:
        print(p)
        exit()

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x = int(readline())
    for i in range(x, 10 ** 10):
        b = True
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                b = False
                break
        if b:
            print(i)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    N = 200000
    f = [1]*N
    p = 2
    prime = []
    while p < N:
        while p < N and not f[p]:
            p += 1
        if p >= N:
            break
        j = 2*p
        prime.append(p)
        while j < N:
            f[j] = 0
            j += p
        p += 1
    x = I()
    print(prime[bisect.bisect_left(prime,x)])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input().strip())

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

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

Submission status: Accepted

Solution code:
n = int(input())

def shave(n):
    if n < 2:
        return []
    else:
        n_root = int(n**0.5)
        candidate = [i for i in range(3, n+1, 2)]
        for i in range(3, n_root+2, 2):
            candidate = [j for j in candidate if j == i or j % i != 0]
        candidate = [2] + candidate
        return candidate

for i in shave(10**5+10):
    if i >= n:
        print(i)
        break

Submission status: Accepted

Solution code:
n = int(input())

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

import bisect
a = primelist(110000)

print(a[bisect.bisect_left(a, n)])

Submission status: Accepted

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

X = int(sys.stdin.buffer.readline())



def get_primes(max=None, count=None):
    """
    素数列挙
    昇順にソートされています
    https://qiita.com/Ishotihadus/items/73e107271275611f05f2
    :param int max:
    :param int count:
    :return:
    """
    assert max or count
    if count:
        raise NotImplementedError()
    if max <= 1:
        return []

    primes = [2]
    sieve = [False for _ in range(max + 1)]
    p = 3
    while p <= max:
        primes.append(p)
        sieve[p] = True
        if p <= math.sqrt(max):
            for i in range(p * (p | 1), max + 1, p * 2):
                sieve[i] = True
        while p <= max and sieve[p]:
            p += 2

    return primes

primes = get_primes(max=X+1000)
for p in primes:
    if p < X:
        continue
    print(p)
    exit()

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


from math import sqrt


def is_prime(x):
    if x == 1:
        return False
    if x % 2 == 0:
        if x == 2:
            return True
        else:
            return False

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

    return True


X = read_a_int()

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

Submission status: Runtime Error

Solution code:
x= int(input())

def prime_check(num,count):
    if (num % count) != 0:
        if num <= count**2:
            return num
        else:
            return prime_check(num,count+1)
    else :
        return prime_check(num+1,2)

if x==2 :
    print (2)
else:
    print(prime_check(x,2))

Submission status: Runtime Error

Solution code:
x= int(input())

def prime_check(num,count):
    if (num % count) != 0:
        if num <= count**2:
            print(num)
        else:
            prime_check(num,count+1)
    else :
        prime_check(num+1,2)

if x==2 :
    print (2)
else:
    print(prime_check(x,2))

Submission status: Runtime Error

Solution code:
# Original Submission At: https://atcoder.jp/contests/abc149/submissions/16823042
x= int(input())

def prime_check(num,count):
  	while True:
        while num % count == 0:
            num = num + 1
            count = 2
    	if num <= count**2:
        	print(num)
            break
        else:
          count = count + 1

if x==2 :
    print (2)
else:
    prime_check(x,2)