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())
b_flg = True
try_n = x - 1
roop_c = 0
if x == 2:
    print(x)
else:
    while b_flg:
        try_n += 1
        for n in range(2, try_n):
            roop_c += 1
            if try_n % n == 0: # 素数でないことが確定した場合
                break
            else:
                if roop_c == try_n - 2:
                    b_flg = False
    print(try_n)

Submission status: Accepted

Solution code:
x =  int(input())
 
def primes(z, 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]) and (i>=z) ]

Prime = primes(x, (10**5)+4)
ans = Prime[0]
print(ans)

Submission status: Accepted

Solution code:
import math

x = int(input())
if x <= 3:
    print(x)
#elif x%2 == 0:
#    x += 1
else:
    if x%2 == 0:
        x += 1
    cnt = 0
    max_search = math.ceil(math.sqrt(x))
    while cnt < max_search-2:
        cnt = 0
        max_search = math.ceil(math.sqrt(x))
        for i in range(2, max_search):
            if x % i == 0:
                break
            else:
                cnt += 1
        x += 2
    print(x-2)

Submission status: Accepted

Solution code:
X = int(input())

while True:
  if X==2:
    break # Xが2の場合素数なのでwhileのループを抜ける
  for n in range(2, X):
    if X%n==0: # 2以上x未満の自然数nでxを割り切れるものが存在したのでxは素数ではない
      X+=1
      break # 一度forループを抜けて次のX+1を素数判定する 
  if n==X-1:
    break # 2以上x未満のすべての自然数でｘを割り切れなかった場合whileのループを抜ける
print(X)

Submission status: Accepted

Solution code:
num = int(input())

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

Submission status: Accepted

Solution code:
def main():
    X = int(input())
    if X < 4:
        print(X)
        return
    d = [3]
    end = int(X / 2) if X > 11 else 12
    for a in range(5, end, 2):
        # print(a, flush=True)
        flag = False
        for m in d:
            if a % m == 0:
                flag = True
                break
        if flag:
            continue
        # ループから抜けている = 素数
        if a >= X:
            print(a)
            return
        else:
            d.append(a)

    if X % 2 == 0:
        X += 1

    for a in range(X, 100004, 2):
        flag = False
        for m in d:
            if a % m == 0:
                flag = True
                break
        if flag:
            continue
        # ループから抜けている = 素数
        print(a)
        return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
x = int(input())
if (x <= 2):
    print(2)
    exit()
ans = 100003
if (x%2 == 0):
    x += 1
for num in range(x, 10**5, 2):
    flag = True
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if(num % i == 0):
            flag = False
            break
    if(flag):
        ans = num
        break
print(ans)

Submission status: Accepted

Solution code:
x = int(input())
prime = [2]
for i in range(3,320,2):
    flag = True
    for j in prime:
        if i%j==0:
            flag = False
            break
    if flag:
        prime.append(i)
if x<=317:
    for i in range(len(prime)):
        if x<=prime[i]:
            print(prime[i])
            break
else:
    for i in range(x,x+100):
        flag = True
        for j in prime:
            if i%j==0:
                flag = False
                continue
        if flag:
            print(i)
            break

Submission status: Accepted

Solution code:
x = int(input())

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

for i in range(2, n//2):
    if L[i]:
        mul = 2
        while i * mul <= n:
            L[i * mul] = False
            mul += 1

for i in range(x, n+1):
    if L[i]:
        print(i)
        break

Submission status: Accepted

Solution code:
import math

n = int(input())

if n == 2:
    print(2)
    exit()
else:
    if n % 2 == 0:
        n += 1

i = 3

m = 2 * math.floor(n/2) + 1

while i < m:
    if n % i == 0:
        i = 3
        n += 2
    i += 2


print(n)

Submission status: Accepted

Solution code:
x=int(input())
for i in range(x,10**9):
    ch=True
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            ch=False
            break
    if ch:
        print(i)
        exit()

Submission status: Accepted

Solution code:
X = int(input())

for i in range(1000):
    logit = X + i
    flag = False
    for j in range(2, logit):
        if logit % j == 0:
            flag = True
            break
    if not flag:
        print(logit)
        break

Submission status: Accepted

Solution code:
# coding:utf-8
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

X = int(input())

l = seachPrimeNum(100003)

for n in l:
    if n >= X:
        print(n)
        exit(0)

Submission status: Accepted

Solution code:
import numpy as np
def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
n=int(input())
pri1=seachPrimeNum(n)
ma=pri1.index(max(pri1))
pri=seachPrimeNum(n*2)
if pri[ma]==n:
    print(n)
else:
    print(pri[ma+1])

Submission status: Accepted

Solution code:
def main():
	# a,b,k = map(int,input().split())
	n = int(input())
	# s = str(input())
	# h = list(map(int,input().split()))
	# l = [list(map(int, input().split())) for _ in range(n)]
	# s = list(s)
	waru = 2
	if n <= 3:
		print(n)

	while n > 3:
		if n == waru:
			# print("break!")
			print(n)
			break
		elif n % waru == 0:
			n += 1
			waru = 2
			
		else:
			waru += 1

		# print(n,waru)
	

if __name__ == '__main__':
	main()

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

n=int(input())
ran = range(n,100004)
res = 0
for num in ran:
  if is_prime(num):
    res = num
    break
    
print(res)

Submission status: Accepted

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

for i in range(x, 200000):
    if check(i) == True:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys

def main():
    X = int(input())
    
    if X == 2:
        print('2')
        sys.exit()

    while True:
        for j in range(2, X):
            if X % j == 0:
                break

            if X % j == 1 and j == X-1:
                print(X)
                sys.exit()
            
        X+=1

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A = int(input())
if A == 2:
    print(2)
    exit()
sosu = [2] #素数が入る
sosu_2 = [4] #素数の2乗の数が入る
sosu_2_index = 1
for num in range(3, 100010, 2):
    if  num > sosu_2[sosu_2_index-1]:
        sosu_2_index += 1
    flag =  True
    for i in range(1,sosu_2_index):
        if num % sosu[i] == 0:
            flag = False
            break
    if flag:
        sosu.append(num)
        if num >= A:
            print(num)
            exit()
        sosu_2.append(num**2)

Submission status: Accepted

Solution code:
import math
import sys
X = int(input())
count = 0
while True:
    for i in range(2,math.ceil(math.sqrt(X))):
        count= 0
        if X%i == 0:
            count += 1
            break

    if count == 0:
        print(X)
        sys.exit()
        break
    X += 1

Submission status: Accepted

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

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

for i in range(X, 10**9):
    if (is_prime(i)):
        print(i)
        break

Submission status: Accepted

Solution code:
from math import sqrt, ceil

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    for i in range(5, ceil(sqrt(n))):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    
    return True

def next_prime(N):
    if (N <= 1):
        return 2
    
    prime = N
    found = is_prime(N)

    while(not found):
        prime += 1

        if (is_prime(prime)):
            found = True
    
    return prime

X = int(input())

print(next_prime(X))

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
  
N = int(input()) - 1
ans_bool = False

while ans_bool==False:
  N = N + 1
  ans_bool = is_prime(N)

print(N)

Submission status: Accepted

Solution code:
# ABC149c


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    # map(int,input().split())
    x = int(input())

    def prime_factorize(n):
        a = []
        while n % 2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.append(n)
        return a

    for i in range(x, x * x):
        if len(prime_factorize(i)) < 2:
            print(i)
            exit(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
l = 10**6
primes = [False] * 2 + [True] * (l - 2)   
for i in range(2, l):
  if primes[i]:
    for j in range(i ** 2, l, i):
      primes[j] = False
x=int(input())
for i in range(x,l):
    if primes[i]:
        print(i)
        break

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

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

Submission status: Accepted

Solution code:
import math
n=int(input())
for k in range(n,2*n,1):
    for p in range(2, int(math.sqrt(k)) + 1):
        if k % p == 0:
            break
    else:
        print(k)
        break

Submission status: Accepted

Solution code:
X = int(input())

def prime(q):
    count = 0
    for i in range(2,q):
        if q%i == 0:
            count = count +1
        else:
            count = count
    if count == 0:
        return 1
    else:
        return 0
  
ans = X
for i in range(X, X**2):
    if prime(i) == 1:
        print(ans)
        break
    else:
        ans =ans + 1

Submission status: Accepted

Solution code:
import math
X = int(input())
search = True
if X == 2:
  search = False
elif X == 3:
  search = False
cnt = 0
if bin(X&1)==bin(0):
  cnt += 1
while search:
  X = X + cnt
  cnt = 2
  tmp = False
  sum = 0
  for x in str(X):
    sum += int(x)
  con = X**(1/2)
  if float(con).is_integer():
    continue
  con = math.floor(con)
  prime = True
  for i in range(con)[3::2]:
    if X % i == 0:
      prime = False
      break
  
  if prime:
    break
print(X)

Submission status: Accepted

Solution code:
x = int(input())
primes = [i for i in range(2, x)]
for i in range(2, int(x ** 0.5 + 0.5)):
    primes = [j for j in primes if j % i != 0 or j == i]
checking = x
while True:
    for p in primes:
        if checking % p == 0:
            break
    else:
        print(checking)
        break
    checking += 1

Submission status: Accepted

Solution code:
import math
 
number = 123
 
def trial_division(target):
    dest = int(math.sqrt(target))
 
    for i in range(2,dest):
        if target % i == 0:
            return 0
    print(target)
    return 1

X = int(input())
flag = True
while flag:
    res = trial_division(X)
    if res == 1:
        flag = False
    X = X + 1

Submission status: Accepted

Solution code:
# coding: utf-8
x=int(input())
flg=True
while flg:
    flg=False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:#素数じゃない
            x+=1
            flg=True
            break
print(x)

Submission status: Accepted

Solution code:
n= int(input())

def isprime(n):
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6

    return True
def fun(n):
    i = n
    while 1:
        if isprime(i):
            break
        i+=1
    return i

print(fun(n))

Submission status: Accepted

Solution code:
x=int(input())
s=[0 for i in range((10**5)+3)]
s[0]+=1
for i in range(1,(10**5)+3,1):
    if s[i]==0:
        for j in range(2,(10**5)+3,1):
            if (i+1)*j>=(10**5)+3:
                break
            else:
                s[(i+1)*j-1]+=1

for k in range(x-1,(10**5)+3,1):
    if s[k]==0:
        print(k+1)
        break

Submission status: Accepted

Solution code:
def chk(n):
  chkMax = pow(n, 0.5)
  i = 2
  while i <= chkMax:
    if n % i == 0:
      return -1
    i += 1
  return 1
  
n = int(input())

while chk(n) == -1:
  n += 1

print(n)

Submission status: Accepted

Solution code:
import math

# 1行目の入力を空白で分割された数値として扱う
X = int(input())

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

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

Submission status: Accepted

Solution code:
def isPrime(n):
    for i in range(2,N):
        if N%i == 0:
            return False
    return True
    
    
def find_next_prime(n):
    return find_prime_in_range(n, 2*n)

def find_prime_in_range(a, b):
    for p in range(a, b):
        for i in range(2, p):
            if p % i == 0:
                break
        else:
            return p
    return None

N = int(input())
if(isPrime(N)):
    print(str(N))
else:
    print(str(find_next_prime(N+1)))

Submission status: Accepted

Solution code:
x = int(input())
def sosu(x):
	tf = True
	for i in range(2,x//2):
		if x % i == 0:
			tf = False
			break
	return tf
a = x
while True:
	if sosu(a) == True:
		break
	a += 1
print(a)

Submission status: Accepted

Solution code:
n=int(input())
a=0
b=0
while a==0:
    x=n+b
    b+=1
    y=0
    for i in range(x-2):
        if x%(2+i)==0:
            y+=1
    if y==0:
        a+=1
print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def Prime(x):
    c=0
    for i in range(math.floor(math.sqrt(x))):
        if i==0:
            c=0
        elif x%(i+1)==0:
            c=c+1
    if c==0:
        return 1
    else:
        return 0
            
            

X=int(input())
Pm=0
while Pm==0:
    if Prime(X)==1:
        Pm=Pm+1
    else:
        X=X+1
print(X)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

Submission status: Accepted

Solution code:
import numpy as np

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]

X = int(input())
prime = np.array(primes(200000))
if sum(prime == X):
    ans = X
else:
    idx = np.array(np.where(prime > X))
    idx = idx[0]
    ans = prime[idx[0]]
print(ans)

Submission status: Accepted

Solution code:
inpt = input()
X = int(inpt)

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

Submission status: Accepted

Solution code:
import random

x = int(input())

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True

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

print(x+i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

x = int(input())

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

Submission status: Accepted

Solution code:
import math
X = int(input())
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)
        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list
l = get_primenumber(10**6)
for i in range(X,10**6):
  if i in l:
    print(i)
    break

Submission status: Accepted

Solution code:
import math

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 = int(input())

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

print(n)

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

while is_prime(x) == False:
    x += 1

print(x)

Submission status: Accepted

Solution code:
import math
x = int(input())
if x == 2 or x == 3:
    print(x)
else:
    i = x
    flag = False
    while i <= 1000000:
        if i % 2 == 0 or i % 3 == 0:
            i += 1
            continue
        for j in range(5, int(math.sqrt(i))+1):
            if i % j == 0:
                break
        else:
            flag = True
        if flag:
            break
        i += 1
    print(i)

Submission status: Accepted

Solution code:
x = int(input())
y = x
for p in range(10000000):
    c = 0
    for i in range(2, y-1):
        if y % i == 0:
            c += 1
    if c == 0:
        print(y)
        break
    else:
        y += 1

Submission status: Accepted

Solution code:
def pr(n):
    c=0
    for i in range(2,int(n**(1/2))+1):
        if n%i==0:
            break
        else:c+=1
    if c==int(n**(1/2))-1:
        return 1
def sol(n):
    s=n
    while pr(s)!=1:
        s+=1
    return s
n= int(input())
print(sol(n))

Submission status: Accepted

Solution code:
import sys
import math
def input(): return sys.stdin.readline().rstrip()

def main():
    x = int(input())
    x_sqrt = int(math.sqrt(x))

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

if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
def checkPrime(num):
    isPrime = True
    for i in range(2,(num//2)+1):
        if(num%i == 0):
            isPrime = False
            break
    return isPrime
def nextPrime(num):
    if(checkPrime(num)):
        return num
    n = num-1 if(num%2==0) else num
    while(True):
        n +=2
        if(checkPrime(n)):
            result = n
            break
    return result

num = int(input())
print(nextPrime(num))

Submission status: Accepted

Solution code:
def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

x = ii()
N = x*10

p = [True]*(N)
p[0] = p[1] = False

for i in range(2, N):
  if not p[i]:
    continue

  for j in range(2*i, N, i):
    p[j] = False

for i in range(x, N):
  if p[i]:
    print(i)
    exit()

Submission status: Accepted

Solution code:
import math
X = int(input())
f = True
if X == 2:
    print(X)
else:
    while f:
        for n in range(2, int(math.sqrt(X)) + 1):
            if X % n == 0:
                X += 1
                break
            if n == int(math.sqrt(X)): 
                print(X)
                f = False
                break

Submission status: Accepted

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

a = primes(10**5+3)
b = [i for i in a if i>=x]
print(b[0])