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

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

while prime(x)==False:
  x += 1
print(x)

Submission status: Accepted

Solution code:
x = int(input())
while any(x%i<1 for i in range(2,int(x**0.5)+1)):
  x+=1
print(x)

Submission status: Accepted

Solution code:
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def fc(n):
    for p in range(2, n):
        if n % p == 0:
            return False
    else:
        return True


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

    N = ii()
    while True:
        if fc(N):
            print(N)
            exit()
        N += 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
x=int(input())
arr=set(range(2,x))
for i in range(2,int(x**0.5)+1):
  arr.difference_update(range(2*i,x,i))
res=True
x-=1
while res:
  res=False
  x+=1
  for i in arr:
    if x%i==0:
      res=True
      break
print(x)

Submission status: Accepted

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

while True:
    d = True
    for i in range(2,int(ans**0.5)+1):
        if ans%i == 0:
            d = False
    if d:
        print(ans)
        exit()
    else:
        ans += 1

Submission status: Accepted

Solution code:
X = int(input())
def is_prime(n):
    if n == 2:
        return True
    elif n%2 == 0:
        return False
    if pow(2, n-1, n) != 1:
        return False
    return True

n = X-1
primes = []
while True:
    n += 1
    if is_prime(n):
        flag = True
        for p in range(3, n//2):
            if n%p == 0:
                flag = False
                break
        if flag:
            primes.append(n)
            if n >= X:
                print(n)
                break

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    x = int(input())

    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res

    while 1:
        if len(prime_decomp(x))==1:
            print(x)
            exit()
        else:
            x += 1

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

while True:
    if sosu(X):#関数内がFalseのとき実行されない
        print(X)
        break
    X+=1

Submission status: Accepted

Solution code:
import math
x=int(input())
for i in range(x,100004):
    flag=True
    for j in range(2,math.floor(math.sqrt(i))+1):
        if i%j==0:
            flag=False
            break
    if flag:
        print(i)
        exit(0)

Submission status: Accepted

Solution code:
N = int(input())
x = True
while x:
    num = 2
    while N % num != 0:
        num += 1
    if num == N:
        x = False
    else:
        N += 1
print(N)

Submission status: Accepted

Solution code:
x = int(input())

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

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

Submission status: Accepted

Solution code:
x = int(input())

ju = True

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

while(is_prime(x)!=True):
    x += 1
print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

X = ir()

def check(n):
    if X == 2:
        return True
    if n % 2 == 0:
        return False
    f = 3
    while f * f <= n:
        if n % f == 0:
            return False
        else:
            f += 2
    return True

while True:
    if check(X):
        print(X); exit()
    else:
        X += 1

# 44

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def prim():
 a=int(input())
 # l=[i for i in range(1,a)]
 l1=[]
 for j in range(0,a):
  for i in range(2,a+j):
      l1.append((a+j)%i)
  if 0 not in l1:
      return a+j
  l1=[]
  # print(a+j)
print(prim())

Submission status: Accepted

Solution code:
import math
n=int(input())
def prime_judge(n):
  if n == 2:
    return True
  if n < 2 or n % 2 == 0:
    return False
  for i in range(3, int(math.sqrt(n)) + 1, 2):
    if n % i == 0:
      return False
  return True

while prime_judge(n)==False:
  n+=1
print(n)

Submission status: Accepted

Solution code:
import math

X = int(input())

def isPrime(x):
  for i in range(2,int(math.sqrt(x))):
    if x % i == 0:
      return False
  return True

while 1:
  if isPrime(X):
    print(X)
    break
  X += 1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math

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


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())

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

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

Submission status: Accepted

Solution code:
n = int(input())
 
flag = 0
 
while flag==0:
#check if n is prime or not
	tst = 2
	while n % tst != 0:
		tst = tst + 1
	if tst==n: 
		flag=1
	else:
		n=n+1
print(n)

Submission status: Accepted

Solution code:
x=int(input())
i=2
cond="notyet"
while cond=="notyet":
    count=0
    for i in range(2,x):
        ex=x%i
        if  ex!=0:
            count+=1
    if count==x-2:
        ans=x
        cond="discovered"
    else:
        x=x+1
print(ans)

Submission status: Accepted

Solution code:
x = int(input())

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

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

Submission status: Accepted

Solution code:
a = int(input())
b = True
def hantei(n, x): #素数だとFalseを返す
    for i in range(2, n):
        if n % i == 0:
            x = True
            return x
while b:
    b = hantei(a, b)
    if b is None:
        print(a)
        break
    a += 1

Submission status: Accepted

Solution code:
a = int(input())
def hantei(x):
    k = 0
    for i in range(2, x//2):
        if x % i == 0:
            k += 1
    if k ==0:
        return x

c = True
while c:
    hantei(a)
    b = hantei(a)
    if b is not None:
        print(b)
        c = False
    elif b is None:
        a += 1

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
n = 100003
a = [False]*2 + [True]*(n-1)
for i in range(2, int(n**.5)+1):
    if not a[i]:
        continue
    for j in range(i*2, n+1, i):
        a[j] = False
b = [i for i in range(n+1) if a[i]]

x = int(input())
print(min(i for i in b if i>=x))

Submission status: Accepted

Solution code:
def main():
	x = int(input())
	while not IsPrime(x):
		x += 1
	print(x)

def IsPrime(n):
	if n < 2:
		return False
	elif n == 2:
		return True
	elif n % 2 == 0:
		return False
	
	sqrtN = int(n**0.5)
	for i in range(3, sqrtN, 2):
		if n%i == 0:
			return False
	return True

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#ABC149.C
X = int(input())
def isPrime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
  
  # nの平方根まで計算する
    m = int(n**0.5) + 1
    for p in range(3, m, 2):
        if n % p == 0:
            return False
    return True
while True:
    if isPrime(X)==True:
        print(X)
        break
    else:
        X+=1

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def is_prime(x):
    if x <= 1:
        return False
    for i in range(2, x + 1):
        if i * i > x:
            break
        if x % i == 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(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,1000000):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
x=int(input())
import math
def is_prime(n):
    if n==1:
        return False
    for divisor in range(2,int(math.sqrt(n))+1):
        if n%divisor == 0:
            return False
    return True

k=0
while True:
    if is_prime(x+k):
        print(x+k)
        break
    else:
        k += 1

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
X = int(input())

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

#print(primes(1000000)[:X])
for i in primes(1000000):
    if i >= X:
        print(i)
        break

Submission status: Accepted

Solution code:
x = int(input())
flag = 0

def judge(x):
    count = 0
    for i in range(1,x+1):
        if x%i == 0:
            count +=1

    return count

while (1):
    if judge(x) == 2:
        print(x)
        break
    else:
        x = x+1

Submission status: Accepted

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


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

for i in range(x, 2*10**5):
    if is_prime(i) == True:
        print(i)
        exit()

Submission status: Accepted

Solution code:
X = int(input())
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]]

tmp = primes(2*X)

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

Submission status: Accepted

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

    print(i)

Submission status: Accepted

Solution code:
import math

def isPrime(n):
    for i in range(math.floor(n ** (1/2))):
        i += 1
        if i == 1:
            pass
        elif n % i == 0:
            return False
            break
    else:
        return True
      
n = int(input())

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

Submission status: Accepted

Solution code:
import math

x = int(input())
y = 0

if x==2: #2だけは例外
  print(2)
  
else: #xの素数判定
  while y == 0: #素数でない間は続ける
    for k in range(2, int(math.sqrt(x)) + 1): #2以上ルートn以下で割り切れるか調べる
      if x % k == 0: #もし割り切れたら、
        x = x + 1 #素数ではないので、xを+1して、
        break #for文を抜けてwhileに戻る
      if k == int(math.sqrt(x)):
        y = 1
  print(x)

Submission status: Accepted

Solution code:
from sys import exit
from math import sqrt

x = int(input())
if x == 2:
    print(2)
    exit()
elif x == 3:
    print(3)
    exit()
i = x
while i <= x * int(sqrt(x)):
    j = 2
    while j <= int(sqrt(i)):
        if not i % j:
            break
        j += 1
    if j > int(sqrt(i)):
        print(i)
        exit()
    i += 1

Submission status: Accepted

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

def check(n):
    for i in range(2, math.ceil(math.sqrt(n))+1):
        #print(i)
        if n%i==0:
            break
    else:
        return 1

if X==2:
    print(2)
else:
    for i in range(X, X+100):
        #print(i)
        if check(i)==1:
            print(i)
            break

Submission status: Accepted

Solution code:
import math

X = int(input())

for i in range(X,2*X,1):
  for j in range(2,math.floor(i**0.5)+1,1):
    if i % j == 0:
      break
  else:
    print(i)
    break

Submission status: Accepted

Solution code:
import math
X = int(input())
flag = False
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
i = 0
while flag != True:
    flag = is_prime(X+i)
    i += 1
print(X+i-1)

Submission status: Accepted

Solution code:
x = int(input())

s =[2]

if x==2:
    print(x)
    exit()
else:
    for i in range(3,int(x/2),2):
        if all(i%k!=0 for k in s):
            s.append(i)

while any(x%k==0 for k in s):
  x+=1
else:
  print(x)

Submission status: Accepted

Solution code:
X=int(input())
while(1):
    if all(X%i for i in range(2,int(X**0.5)+1)):
        print(X)
        break
    X+=1

Submission status: Accepted

Solution code:
import math

def check_prime(a):
    b = True
    for i in range(2,int(math.sqrt(a))):
        if a % i==0:
            b = False
            break
    if a==2:b = True
    return b      
a=int(input())
while True:
    if check_prime(a):
        print(a)
        break
    a += 1

Submission status: Accepted

Solution code:
X = int(input())

primes = list(range(2 * X + 1))
primes[1] = 0

for prime in primes:
    if prime > (2*X)**0.5:break
    if prime == 0:continue
    for non_prime in range(2 * prime, 2*X+1, prime):
        primes[non_prime] = 0
lst = [prime for prime in primes if prime != 0]

for i in lst:
    if i>=X:
        print(i)
        break

Submission status: Accepted

Solution code:
from math import sqrt

MAX = 10**5 + 10
x = int(input())

nums = [i for i in range(1, MAX)]

for i in range(2, int(sqrt(MAX))+1):
    nums = [j for j in nums if j % i != 0 or j == i]
l = 0
r = len(nums)-1
while r - l > 1:
    mid = (r + l)//2
    if nums[mid] <= x:
        l = mid
    else:
        r = mid
if nums[l] == x:
    print(x)
else:
    print(nums[r])

Submission status: Accepted

Solution code:
import math

n=int(input())

def check(n):
  start=int(math.sqrt(n)//1)
  for i in range(2,start+1):
    if (n%i==0):
      return "False"
  return "True"

for i in range (n,100004):
  if (check(i)=="True"):
    print(i)
    break

Submission status: Accepted

Solution code:
import sys
import math

x=int(input())

for i in range(x,200000):
    flag = True
    tmp = math.floor(math.sqrt(i))
    for k in range(2,tmp):
        if i%k == 0:
            flag = False
    if flag:
        print(i)
        sys.exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
X = int(input())
ans = 0
for i in range(X,X+100):
  for j in range(2,int(math.sqrt(i))):
    if i % j == 0:
      ans += 1
  if ans == 0:
    print(i)
    exit()
  ans = 0

Submission status: Accepted

Solution code:
import math

N=int(input())

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

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

    return True

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

Submission status: Accepted

Solution code:
x = int(input())

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

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

Submission status: Accepted

Solution code:
x = int(input())

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

Submission status: Accepted

Solution code:
p = int(input())
n = 2*p
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)
primes.sort()

for i in primes:
    if i >= p:
        print(i)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x=int(input())
a=0
i=x
t=0
ans=0
while t==0:
	a=0 
	for k in range(2,round(i**0.5)+1):
		if i%k==0:
			a=a+1
	if a==0:
		t=i
	i=i+1
print(t)

Submission status: Accepted

Solution code:
def search_num(X):
    ans=1
    for i in range(2,X):
        if X%i==0:
            ans*=2
    if ans%2!=0:
        return X
    else:
        return search_num(X+1)
X=int(input())
print(search_num(X))

Submission status: Accepted

Solution code:
X = int(input())

candidate = X
prime = False

if candidate == 2:
    prime = True

while prime != True:
    for i in range(2, int(candidate ** 0.5) + 2):
        if candidate % i == 0:
            candidate += 1
            break
    else:
        prime = True

print(candidate)

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())
judge = ""

if X == 2:
    print(2)
else:
    while judge != "prime":
        for i in range(2, X):
            if X % i == 0:
                judge = "com"
                X += 1
                break
            else:
                judge = "prime"
    print(X)

Submission status: Accepted

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

x = int(input())
p = primes(10**6)

while True:
    if p[x]:
        break
    else:
        x += 1
print(x)

Submission status: Accepted

Solution code:
n = int(input())

def prime_or(num):
    mx = int(num**(1/2))
    
    for i in range(2,mx):
        if(num%i == 0):
            return 0
    
    return 1
    
flag = 0
st = n
while True:
    if(prime_or(st)==1):
        print(st)
        break
    else:
        st += 1

Submission status: Accepted

Solution code:
def factorize(n):
    result = []
    tmp = n
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while tmp % k == 0:
            cnt += 1
            tmp //= k
        if cnt > 0:
            result.append([k, cnt])
    if tmp != 1:
        result.append([tmp, 1])
    return result

x = int(input())

while True:
    f = factorize(x)
    if len(f) == 1:
        if f[0][1] == 1:
            print(x)
            break
    x += 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,x-1):
    if x % j == 0:
      x += 1
      break
    elif j == x-2:
      print(x)
      exit()

Submission status: Accepted

Solution code:
X = int(input())

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


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x=int(input())
#n,m=map(int,input().split())
#pl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
import math

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

Submission status: Accepted

Solution code:
import math
X = int(input())
for i in range(X, 2*X):
  frag = False
  for j in range(2, math.ceil(math.sqrt(i))):
    if i % j != 0:
      continue
    else:
      break
  else:
    print(i)
    frag = True
  if frag:
    break

Submission status: Accepted

Solution code:
X=int(input())
def chk_prime(x):
    for i in range(2,int(pow(x,0.5))+1):
        if x%i==0:
            return False
    return True

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

Submission status: Accepted

Solution code:
def is_prime(x):
  if x < 2:
    return False
  if x == 2 or x == 3 or x == 5:
    return True
  if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
    return False
  prime = 7
  step = 4
  while prime <= pow(x, 1/2):
      if x % prime == 0:
        return False
      prime += step
      step = 6 - step
  return True


res = int(input())
p = res
flg = 0
while flg == 0:
  if is_prime(p) and p >= res:
    res = p
    flg = 1
  p += 1
print(res)

Submission status: Accepted

Solution code:
import math

x = int(input())

def Eratos(n):
    P,L = [],[True for _ in range(n+1)]
    for i in range(2,int(math.sqrt(n))+1):
        if L[i]:
            for j in range(2,n//i+1):
                L[i*j] = False
    for i in range(2,n+1):
        if L[i]:
            P.append(i)
    return P

def b_search(A,key,left,right):
    mid = (left+right)//2
    if key <= A[0]:
        return A[0]
    elif key > A[len(A)-1]:
        return 10**9
    else:
        if A[mid] < key and key <= A[mid+1]:
            return A[mid+1]
        elif key > A[mid]:
            return b_search(A,key,mid,right)
        else:
            return b_search(A,key,left,mid)

P = Eratos(10**6)
ans = b_search(P,x,0,len(P))
print(ans)

Submission status: Accepted

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

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

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

i = x
while(i > 0):
    if is_prime(i):
        print(i)
        i = -1
    else:
        i+=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
  
n = int(input())
while not is_prime(n):
  n += 1
print(n)

Submission status: Accepted

Solution code:
from math import sqrt


def prime_check(a):
    for i in range(int(sqrt(a))):
        if a % (i + 2) == 0:
            return False
    return True


x = int(input())

if x != 2:
    while not(prime_check(x)):
        x += 1

print(x)

Submission status: Accepted

Solution code:
def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  for p in range(2, n):
      if n % p == 0:
        return False
  return True
def main():
    X = int(input())
    while True:
        if isPrime(X) == True:
            print(X)
            break
        X += 1
main()

Submission status: Accepted

Solution code:
x = int(input())
def primechecker(n):
    if n != 2:
        for i in range(2,n):
            if n % i == 0:
                return False
                break
        return True
    else:
        return True
#
while primechecker(x) == False:
    x += 1

print(x)

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

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

Submission status: Accepted

Solution code:
X = int(input())

def is_prime(n):
  factors = []
  f = 2
  while f**2 <= n:
    if n % f == 0:
      n //= f
      factors.append(f)
    else:
      f += 1
  if len(factors) == 0:
    return True
  else:
    return False

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

Submission status: Accepted

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

Submission status: Accepted

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

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

i=x
while prime(i)==False:
    i+=1
print(i)

Submission status: Accepted

Solution code:
import math

x = int(input())


def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))


for n in range(100005):
    if n >= x and is_prime(n):
        print(n)
        break

Submission status: Accepted

Solution code:
x = int(input())
for i in range(x, 10**6):
    for n in range(2, i):
        if i % n == 0:
            break

    else:
         print(i)
         break

Submission status: Accepted

Solution code:
# ABC149C - Next Prime
def is_prime_miller_rabin(n: int) -> bool:
    """Miller–Rabin primality test in O(k log^3 n).
    https://twitter.com/kiri8128/status/1241033090773860353
    https://www.wikiwand.com/en/Miller%E2%80%93Rabinprimalitytest
    """
    # cut out small primes and 87% of composite numbers.
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}:
        return True
    elif (
        n % 2 == 0
        or n % 3 == 0
        or n % 5 == 0
        or n % 7 == 0
        or n % 11 == 0
        or n % 13 == 0
        or n % 17 == 0
        or n % 19 == 0
        or n % 23 == 0
        or n % 29 == 0
        or n % 31 == 0
        or n % 37 == 0
        or n % 41 == 0
        or n % 43 == 0
        or n % 47 == 0
        or n % 53 == 0
        or n % 59 == 0
        or n % 61 == 0
        or n % 67 == 0
    ):
        return False

    # find the most suitable witnesses for n
    if n < 2047:
        witnesses = [2]
    elif n < 1373653:
        witnesses = [2, 3]
    elif n < 9080191:
        witnesses = [31, 73]
    elif n < 25326001:
        witnesses = [2, 3, 5]
    elif n < 3215031751:
        witnesses = [2, 3, 5, 7]
    elif n < 4759123141:
        witnesses = [2, 7, 61]
    elif n < 1122004669633:
        witnesses = [2, 13, 23, 1662803]
    elif n < 2152302898747:
        witnesses = [2, 3, 5, 7, 11]
    elif n < 3474749660383:
        witnesses = [2, 3, 5, 7, 11, 13]
    elif n < 341550071728321:
        witnesses = [2, 3, 5, 7, 11, 13, 17]
    elif n < 3825123056546413051:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23]
    elif n < 318665857834031151167461:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    else:  # precisely, n < 3317044064679887385961981 (3.3 * 10^24)
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    d = n - 1
    d = d // (d & -d)

    for a in witnesses:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True


def main():
    N = int(input())
    if N != 2 and N % 2 == 0:
        N += 1
    while not is_prime_miller_rabin(N):
        N += 2
    print(N)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

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

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


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

    # Xから素数判定をすればよい
    x = X
    while not is_prime(x):
        x += 1
    print(x)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
x = int(input())
for i in range(x, 2*x):
  n = 0
  for j in range(2, i+1):
    if i % j == 0:
      n += 1
  if n == 1:
    print(i)
    quit()

Submission status: Accepted

Solution code:
n = int(input())
tmp = n

def is_prime(x):
    if (x==0 or x==1):
        return False
    for n in range(2,x-1):
        if (x % n) == 0:
            return False
    else:
        return True
    
while True:
    if is_prime(tmp):
        print(tmp)
        break
    else:
        tmp += 1