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 math
from math import gcd
INF = float("inf")

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

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

if __name__=="__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
import math


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

x = inint()

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


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

Submission status: Accepted

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

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

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

solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X = int(input())

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

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

Submission status: Accepted

Solution code:
X = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X = int(input())

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

Submission status: Accepted

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

X = int(input())

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
X = int(input())
if X == 2 or X == 3:
    print(X)
else:

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

Submission status: Accepted

Solution code:
x=int(input())

for i in range(x,10**6+1):
  now=i-1
  flag=0
  while(2<=now):
    if i%now==0:
      flag=1
      break
    now-=1
  if flag==0:
    print(i)
    break

Submission status: Accepted

Solution code:

def sieve(n):
    prime = []

    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, n + 1):
        if is_prime[i]:
            prime.append(i)

            for j in range(2 * i, n + 1, i):
                is_prime[j] = False

    return prime, is_prime


N = int(input())
prime, _ = sieve(10 ** 5 + 10)
for v in prime:
    if v >= N:
        print(v)
        break

Submission status: Accepted

Solution code:
from math import sqrt as r
from math import floor as f
X = int(input())
going = True

def judge(X):
    for i in range(3, f(r(X)) + 1, 2):
        if X % i == 0:
            return False
    return True

if X == 2 or X == 3:
    print(X)
    going = False
elif X % 2 == 0:
    X += 1

while going:
    if judge(X):
        print(X)
        break
    X += 2

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())
print(min(i for i in range(x, 100004) if is_prime(i)))

Submission status: Accepted

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

import sys


TEST_INPUT = \
"""

100000

"""

TEST_OUTPUT = \
"""

100003

"""


def primes(n):
    if n == 0 or n == 1: return []
    
    ps = [2]
    for odd in range(3, n + 1, 2):
        for p in ps:
            if odd % p == 0:
                break
            if p ** 2 > odd:
                ps.append(odd)
                break
    return ps


def isprime(n):
    if n == 0 or n == 1: return False
    
    last = int(n**.5)
    for m in primes(last):
        if n % m == 0:
            return False
    return True


def nextprime(n):
    if n in primes(n):
        return n
    else:
        i = n
        while not isprime(i):
            i += 1
        return i


def main(stdin):
    n = int(stdin)
    print(nextprime(n))


if __name__ == "__main__":
    main(sys.stdin.read().strip())

Submission status: Accepted

Solution code:
# ABC149 C - Next Prime

x = int(input())
for i in range(x,10**5+4):
    if all(i%j!=0 for j in range(2,x)):
        print(i)
        break

Submission status: Accepted

Solution code:
import math

X = int(input())

num = [True] * (X * 2 + 1)

t = min(X * 2 + 1, int(math.sqrt(X) + 10))

for i in range(2, t):
    if num[i]:
        for j in range(2, (X * 2) // i):
            num[i * j] = False

for i in range(X, X * 2):
    if num[i]:
        print(i)
        exit()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = 100010
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)

X = int(input())
print(primes[bisect_left(primes,X)])

Submission status: Accepted

Solution code:
def is_prime(num: int) -> bool:
    # 6k +- 1 <= √n
    if num <= 1:
        return False

    if num <= 3:
        return True

    if num % 2 == 0 or num % 3 == 0:
        return False

    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i+2) == 0:
            return False
        i += 6

    return True


x = int(input())
for i in range(x,1000000):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
def prime_num(n):
    f = 3
    while f * f <= n:
        if n % f == 0:
            return 1
        f += 2
    return 0

x = int(input())
if x == 2:
    print(x)
    exit()
prime = (x//2)*2 + 1
while 1 == 1:
    if prime_num(prime) == 0:
        print(prime)
        exit()
    prime += 2

Submission status: Accepted

Solution code:
def primes(n):
    import math
    max = math.sqrt(n)
    candidates = [i for i in range(2, n+1)]
    primes = []
    while candidates[0] <= max:
        primes.append(candidates[0])
        candidates = [candidates[i] for i in range(len(candidates)) if candidates[i] % candidates[0] != 0]
    primes.extend(candidates)
    return primes

def resolve():
    X = int(input())
    _primes = primes(10**5+4)
    import bisect
    print(_primes[bisect.bisect_right(_primes, X)] if X not in _primes else X)



if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:

# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n

from itertools import count

X = int(input())

for x in count(X):
    if len(tuple(prime_factors(x))) == 1:
        print(x)
        break

Submission status: Accepted

Solution code:
class PrimeFactor():

    def __init__(self, n):                  # エラトステネス　O(N loglog N)
        self.n = n
        self.table = list(range(n+1))       # 最小素因数のリスト
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                for q in range(p * p, n + 1, 2 * p):
                    if self.table[q] == q:
                        self.table[q] = p

    def is_prime(self, x):  # 素数判定　O(1)
        if x < 2:
            return False
        return self.table[x] == x

p = PrimeFactor(10**6)

X = int(input())

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

Submission status: Accepted

Solution code:
N = int(input())

candidates = [True]*(2*(10**5)+1)
candidates[0] = candidates[1] = False

for i in range(2, N):
    for j in range(i, 2*(10**5)+1, i):
        candidates[j] = False

for n, n_is_prime in enumerate(candidates):
    if n_is_prime:
        print(n)
        break

Submission status: Accepted

Solution code:
def prime_eratosthenes_edit(n):
    prime_list = []
    num_set = set()
    for i in range(2, 10 ** 6):
        if i not in num_set:
            prime_list.append(i)
            if n <= i:
                return i
            for j in range(i * i, 10 ** 6, i):
                num_set.add(j)


print(prime_eratosthenes_edit(int(input())))

Submission status: Accepted

Solution code:
a = int(input())

import math
def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

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

Submission status: Accepted

Solution code:
import sys, math
lines = [s.rstrip("\n") for s in sys.stdin.readlines()]
x = int(lines.pop(0))

def iter_primes():
    _primes = []
    for n in range(2, 10 ** 6):
        is_prime = True
        upper_limit = math.floor(math.sqrt(n))
        for p in _primes:
            if n % p == 0:
                is_prime = False
                break
            if p >= upper_limit:
                break
        if is_prime:
            _primes.append(n)
            yield n

for n in iter_primes():
    if x <= n:
        print(n)
        break

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

X = I()

# def is_prime(X,n):
#     # if n == 1:
#     #     return False
#     # for i in range(2,int(n**0.5)+1):
#     for i in range(2,X):
#         if n % i == 0:
#             return False
#     return 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
            
for i in range(X,100003+1):
    # print(i)
    if is_prime(i):
        print(i)
        break

#H,N = LI()
#AB = [LI() for _ in range(N)]
#A,B = zip(*AB)
#Ap = np.array(A)
#C = np.zeros(N + 1)

# if ans:
#     print('Yes')
# else:
#     print('No')

Submission status: Accepted

Solution code:
import math

x = int(input())
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import math


def trial_division(target):
    dest = int(math.sqrt(target))

    for i in range(2, dest):
        if target % i == 0:
            return trial_division(target + 2)

    else:
        return target


def main():
    x = int(input())
    if x % 2 == 0 and x != 2:
        x += 1
    ans = trial_division(x)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import bisect
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
result=[]
a=int(input())
for i in range(a-500,a+501):
    if i<0:
        continue
    if is_prime(i):
        result.append(i)
bisect.insort_left(result,a)
n=bisect.bisect_left(result,a)
print(result[n+1])

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    return n

def main(n):
    if n==2:
        return 2
    
    nmax=2*10**5
    isprime=[1]*(nmax)
    isprime[0]=0
    isprime[1]=0
    m=4
    while(m<nmax):
        isprime[m]=0
        m+=2
    
    for i in range(3,nmax,2):
        if isprime[i]==0:
            continue
        else:
            if i>=n:
                return i
        m=2*i
        while(m<nmax):
            isprime[m]=0
            m+=i
    return -1

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

Submission status: Accepted

Solution code:
n=int(input())
while True:
  judge=False
  count = 0
  for i in range(2, n):
    if n%i==0:
      n+=1
      judge=True
      break
  if judge: continue
  print(n)
  break

Submission status: Accepted

Solution code:
import math
 
X = int(input())
ans = 0
 
while ans == 0:
  factor = 0
  if X % 2 == 0 and X != 2:
    X +=1
    continue      
  for divisor in range(2, X // 2):
    if X % divisor == 0:
      factor += 1          
  if factor == 0:
    ans =X
  X +=1    
    
print(ans)

Submission status: Accepted

Solution code:
X = int(input())-1
flag = True

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

Submission status: Accepted

Solution code:
x = int(input())

nums = [True]*(10**6)
n = int(10**6**0.5)
for i in range(4, 10**6, 2): nums[i] = False
for i in range(3, n, 2):
  if nums[i]:
    for j in range(i+i, 10**6, i): nums[j] = False
      
while True:
  if nums[x]:
    print(x)
    break
  x += 1

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    x=INT()
    for i in range(x,100004):
        flg=1
        lim=int(x**0.5+1)
        for k in range(2,lim):
            if i%k==0:
                flg=0
                break
        if flg==1:
            print(i)
            break
if __name__ == '__main__':
    do()

Submission status: Accepted

Solution code:
X=int(input())
import sys
for i in range(X,10**5+1000):
  T=True
  for j in range(2,i):
    if i%j==0:
      T=False
  if T==True:
    print(i)
    break
  else:
    continue

Submission status: Accepted

Solution code:
import math
X = 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 1:
    r = is_prime(X)
    if r:
        break
    X += 1
print(X)

Submission status: Accepted

Solution code:
import math
def isPrime(a):
    mx = math.sqrt(a)
    tmp = 2
    while tmp <= mx:
        if a % tmp == 0:
            return False
        tmp += 1
    return True

x = int(input())
tmp = 0
while True:
    if isPrime(x + tmp):
        f = 1
        print(x+tmp)
        break
    tmp += 1

Submission status: Accepted

Solution code:
X = int(input())-1

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

    if i==R-1:
      break

  print(X)

Submission status: Accepted

Solution code:
X=int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def prime_check(x):
  if x == 2:
    return True
  limit = math.floor(math.sqrt(x)+1)
  cnt = 0
  for i in range(2,limit):
    if x%i == 0:
      cnt += 1
  if cnt == 0:
    return True
  else:
    return False
  
X = int(input())

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

Submission status: Accepted

Solution code:
# 素数ならTrue、素数でなければFalseを返す
def is_prime(x):
    sqrt = int(x ** 0.5)
    for i in range(2, sqrt + 1):
        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:
import bisect
def seive():
  l[0]=0
  l[1]=0
  for i in range(2,10**6+1):
    if l[i]==1:
      k.append(i)
      for j in range(i*i,10**6+1,i):
        l[j]=0
l=[1]*(10**6+1)
k=[]
seive()
#print(len(k))
n=int(input())
d=bisect.bisect_left(k,n)
print(k[d])

Submission status: Accepted

Solution code:
import numpy as np

x = int(input())
is_p = np.array([True] * (2*x+1))

for i in range(2, 2*x+1):
    if is_p[i]:
        is_p[i::i] = False
        if i >= x:
            print(i)
            exit()

Submission status: Accepted

Solution code:
X = int(input())
lsx = [1]*(2*10**5)

for i in range(2,2*10**5):
    if lsx[i] == 1:
        for j in range(i,2*10**5//i):
            lsx[j*i] = 0

for i in range(X,2*10**5):
    if lsx[i] == 1:
        print(i)
        break

Submission status: Accepted

Solution code:
from sys  import stdin,stdout

import bisect

import math

def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")

def soe(limit):
    l=[1]*(limit+1)
    prime=[]
    for i in range(2,limit+1):
        if l[i]:
            for j in range(i*i,limit+1,i):
                l[j]=0

    for i in range(2,limit+1):
        if l[i]:
            prime.append(i)
    return prime

def segsoe(low,high):
    limit=int(high**0.5)+1
    prime=soe(limit)
    n=high-low+1
    l=[0]*(n+1)
    for i in range(len(prime)):
        lowlimit=(low//prime[i])*prime[i]
        if lowlimit<low:
            lowlimit+=prime[i]
        if lowlimit==prime[i]:
            lowlimit+=prime[i]
        for j in range(lowlimit,high+1,prime[i]):
            l[j-low]=1
    for i in range(low,high+1):
        if not l[i-low]:
            if i!=1:
                print(i)

def power(a,n):
    r=1
    while n:
        if n&1:
            r=(r*a)
        a*=a
        n=n>>1
    return r

l=soe(10**6 +100)

def solve():
    n=inp()
    a=bisect.bisect_left(l,n)
    
    print(l[a])



for _ in range(1):
    solve()

Submission status: Accepted

Solution code:
X = int(input())
a = []
c = []
if X % 2 == 1:
    while a == []:
        for i in range(3,X,2):
            b = X % i
            a.append(b)
        if 0 in a:
            a = []
            X += 1
        else:
            print(X)
elif X == 2:
    print(X)
else:
    X += 1
    while c == []:
        for i in range(3,X,2):
            d = X % i
            c.append(d)
        if 0 in c:
            c = []
            X += 1
        else:
            print(X)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x = int(input())

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

while True:
    if not judge_prime_number(x):
        x += 1
        continue
    else:
        print(x)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1
x = int(input())
while not is_prime(x):
    x += 1

print(x)

Submission status: Accepted

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

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
# print(callIsPrime(100000+4)[-1])

for i in callIsPrime(100000+4):
    if i>=x:
        print(i)
        sys.exit()

Submission status: Accepted

Solution code:
import math
from bisect import bisect_left

X = int(input())

def primes_ref(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0
    x_sqrt = math.sqrt(x)

    for prime in primes:
        if prime == 0: continue 
        if prime > x_sqrt: break
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

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

def find_ge(a, x):
  i = bisect_left(a, x)
  if i != len(a):
    return a[i]
  raise ValueError

primes = primes_ref(min(X * X, 100004))
print(find_ge(primes, X))

Submission status: Accepted

Solution code:
x = int(input())

import math
primes=[2]
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  m = math.floor(math.sqrt(n))
  for p in primes:
      if n % p == 0:
        return False
      if p > m:
        break
  primes.append(n)
  return True

for i in range(2,x):
  isPrime(i)

n = x
while(True):
  if isPrime(n):
    print(n)
    exit(0)
  elif n > 10**6:
    exit(0)
  n += 1

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
# 149C Next Prime
#

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

if __name__ == "__main__":
    n = input()
    num = int(n)
    while True:
        if isPrime(num):
            print(num)
            break
        num += 1

Submission status: Accepted

Solution code:
X = int(input())
primes = [1] * (10 ** 6) 
n = 1
primes[0] = 0
primes[1] = 0
while True:
    n += 1
    if primes[n] == 0:
        continue
    if n >= X:
        print(n)
        break
    i = 2
    while i * n < len(primes):
        primes[i * n] = 0
        i += 1

Submission status: Accepted

Solution code:
X = int(input())

n = 10**6
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

for i, p in enumerate(is_prime):
    if i >= X and p is True:
        print(i)
        break

Submission status: Accepted

Solution code:
n = int(input())
primes = []
def is_prime(k):
    if k < 2:
        return False
    if k == 2:
        return True
    for p in primes:
        if k % p == 0:
            return False
        if k <= p*p:
            break
    return True


for i in range(1000000 + 100):
    if is_prime(i):
        primes.append(i)
        if i >= n:
            print(i)
            break

Submission status: Accepted

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

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