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

x = int(input())

j = True

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

while j:
  j = isPrime(x)
  x += 1
  
print(x-1)

Submission status: Accepted

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

x=int(input())

while not(prime(x)):
    x+=1

print(x)

Submission status: Accepted

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

# 整数xが素数かどうかを判定する
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

for i in range(a,a+10**5):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#nの素数判定
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

a = int(input())

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

Submission status: Accepted

Solution code:
import math


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


x = int(input())

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

Submission status: Accepted

Solution code:
#C
X=int(input())
while True:
    a=1
#素数判定
    for i in range(1,int(X**0.5)+1):
        if i ==1:
            continue
        elif a*i==0:
            break
        elif X%i==0:
            a=0
    if a==0:
        X=X+1
    else:
        print(X)
        break

Submission status: Accepted

Solution code:
import sys

K=int(input())
if K==2 or K==3:
  print(K)
elif K==4:
  print(2)
else:
  while True:
    for i in range(2,K//2):
      if K%i!=0:
        if i==(K//2)-1:
          print(K)
          sys.exit()
        continue
      else:
        K=K+1
        break

Submission status: Accepted

Solution code:
import math

X = int(input())
 #素数判定はsqrt(X)までで十分

flag_1 = True
flag_2 = True

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

Submission status: Accepted

Solution code:
import math
def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n%i ==0:
            return False
    return True
 
target = int(input())
 
not_found_flg = True
if target == 2:
    print("2")
else:
    if target %2 == 0:
        target = target+1
    result = 0

    while not_found_flg:
        if (is_prime(target)):
            result = target
            break
        target = target+2
 
    print(result)

Submission status: Accepted

Solution code:
X=int(input())
dp=[True]*(10**5+10000)
dp[0]=False
dp[1]=False
for i in range(2,len(dp)):
  if dp[i]:
    for j in range(i*2,len(dp),i):
      dp[j]=False
      
for i in range(X,len(dp)):
  if dp[i]:
    print(i)
    break

Submission status: Accepted

Solution code:
from bisect import bisect_right
x = int(input())
def primes(n):
    ass = []
    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 in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass
ass = primes(x+10000)
# ass = [-1*i for i in primes(x+1000)]
# ass.reverse()
i = bisect_right(ass, x)
if ass[i-1] == x:
    print(x)
else:
    print(ass[i])

Submission status: Accepted

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

for i in range(x,10**100+1):
    flag = 1
    max = math.floor(math.sqrt(x))

    for j in range(2,max+1):
        if i % j == 0:
            flag = 0
    
    if flag == 1:
        num = i
        break

print(num)

Submission status: Accepted

Solution code:
X = int(input())

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

for i in range(X+1):
    ans = X + i
    if isPrime(ans):
        break
    
print(ans)

Submission status: Accepted

Solution code:
import math as mt
x = int(input())
if x == 2:
    ans = 2
else:
    over = int(mt.sqrt(x))+1
    
    for i in range(x,x+100):
        rpf = True
        for j in range(2,over):
            if i % j == 0:
                rpf = False
                break
        if rpf == True:
            ans = i
            break
        over += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def primes(n):
    memo = [True] * (n + 1)
    i = 2
    while i * i <= n:
        if memo[i]:
            j = i << 1
            while j <= n:
                memo[j] = False
                j += i
        i += 1
    return [i for i in range(n + 1) if memo[i] and i >= 2]

X = int(input())
table = primes(100003)

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

Submission status: Accepted

Solution code:
X = int(input())

while True:
    if X == 1 or X == 2:
        print(X)
        break
    
    cond = True
    for x in range(2, X//2+1):
        if X % x == 0:
            cond = False
            break
    if cond:
        print(X)
        break
    else:
        X += 1

Submission status: Accepted

Solution code:
X = int(input())
prime = [X + i for i in range(X)]
ans = []
for pri in prime:
  anser = [i for i in range(2, pri) if pri % i == 0]
  ans.append(pri)
  if len(anser) == 0:
    break
print(ans[-1])