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())
a=0
while a==0:
    count=0
    div=1
    while div<=x:
        if x%div==0:
            count+=1
        div+=1
    if count==2:
        print(x)
        exit()
    x+=1

Submission status: Accepted

Solution code:
import math

X=int(input())

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

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    x = II()
    def checkP(x):
        if x == 2 or x == 3:
            return True
        for i in range(3,int(x**0.5+1),2):
            if x % i == 0:
                return False
        return True
    
    if x == 2:
        print(2)
        return
    if x % 2 == 0:
        x += 1
    while True:
        if checkP(x):
            print(x)
            return
        else:
            x += 2


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def f(n):
    if n<2:
        return False
    elif n==2:
        return True
    elif n%2==0:
        return False
    sqn=int(math.sqrt(n))
    for i in range(3,sqn+5):
        if n%i==0:
            return False
    return True

def ans():
    for i in range(x,x*2+1):
        if f(i):
            print(i)
            return
ans()

Submission status: Accepted

Solution code:
X = int(input())
ans = 0
def prime(x):
  ret = True
  for j in range(2,int(x**(1/2)+1)):
    if i%j==0:
      ret = False
      break
  return ret

for i in range(X,(10**5)+100):
  if prime(i):
    ans = i
    break
    
print(ans)

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):
  if(is_prime(x+i)):
    break
print(x+i)

Submission status: Accepted

Solution code:
X = int(input())


import math
def get_sieve_of_eratosthenes(n):
    if n==1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

result = get_sieve_of_eratosthenes(200000)
ans = [i for i in result if (i>=X  and i <= X*3)]
print(min(ans))

Submission status: Accepted

Solution code:
import math


def sosu(x):
    if x <= 3:
        return True
    else:
        n = math.ceil(math.sqrt(x))
        for i in range(2, n):
            if x % i == 0:
                return False
        return True


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

Submission status: Accepted

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


primes = prime_factorize(x)
while len(primes) > 1:
    x += 1
    primes = prime_factorize(x)
print(x)

Submission status: Accepted

Solution code:
import math
import bisect

# 素数判定関数
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

# 関数の呼び出し
X=int(input())
Y=callIsPrime(100007)
#print(callIsPrime(100007))

#print(bisect.bisect_right(Y,X)) #二分探索
i=bisect.bisect_left(Y,X)
print(Y[i])

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

def main():
    X = int(input())
    for i in range(X, 10**12):
        if is_prime(i):
            print(i)
            exit()




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

X = int(input())

def trial_division(target):
    dest = int(math.sqrt(target))
 
    for i in range(2,dest):
        if target % i == 0:
            return False
            
    return True
    
myans = False    

while myans == False:
    myans = trial_division(X)
    X += 1
    
print(X-1)

Submission status: Accepted

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

X = int(input())
isp = makePrimeChecker(2 * X)
ans = 0
for i in range(X, 2 * X):
	if(isp[i]):
		ans = i
		break

print(ans)

Submission status: Accepted

Solution code:
import math
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    search_list = list(range(2,number+1))
    while True:
      if search_list[0] > math.sqrt(number):
        prime_list.extend(search_list)
        break
      else:
        head_num = search_list[0]
        prime_list.append(head_num)
        search_list.pop(0)
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

#input = raw_input
a = get_primenumber(10**5+4)
n = int(input())
for val in a:
    if val >= n:
        print(val)
        break

Submission status: Accepted

Solution code:
from fractions import gcd
import sys

input = sys.stdin.readline

x = int(input())

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

def get_prim(x):
    i = x
    while True:
        if is_prime(i):
            return i

        i += 1


print(get_prim(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 [i for i in range(n + 1) if is_prime[i]]

answer = primes(10**5+3)

from bisect import bisect_left

print(answer[bisect_left(answer,int(input()))])

Submission status: Accepted

Solution code:
X = int(input())

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

Submission status: Accepted

Solution code:
n=int(input())

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

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

print (n)

Submission status: Accepted

Solution code:
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    return is_prime
x=int(input())
ans=sieve(2*10**5)
for i in range(x,2*10**5):
    if ans[i-1]:
        print(i)
        exit()

Submission status: Accepted

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

def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
  
while True:
  if is_prime(x):
    print(x)
    break
  else:
    x+=1

Submission status: Accepted

Solution code:

#%%
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=(10**5) * 2):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
l = callIsPrime((10**5) * 2)
#print(l)

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

import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

for i in range(X, 10**6):
    if is_prime3(i) == True:
        print(i)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

lst = get_sieve_of_eratosthenes(2*10**5)
x = I()
for i in lst:
    if x <= i:
        print(i)
        quit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!python3


def f(n):
    for i in range(3, int(n**.5), 2):
        if n % i == 0:
            return False

    return True


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

    if X <= 3:
        print(X)
        return

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

    import sys

    for i in range(X, sys.maxsize, 2):
        if f(i):
            print(i)
            break

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(X: int):
    while True:
        f = 1
        for i in range(2, int(X**0.5) + 1):
            if X % i == 0:
                X += 1
                f = 0
                break
        if f == 1:
            print(X)
            exit()
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

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())
for i in range(100000):
    ans = X + i
    if is_prime(ans):
        break
print(ans)

Submission status: Accepted

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


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]

    
def main():
    X = int(input())
    N = [True] * 110000
    N[0] = False
    N[1] = False  

    n = 2
    while n < X:
        if N[n]:
            for s in range(1, 110000 // n):
                N[n * s] = False
            n += 1
            continue
        else:
            n += 1


    while not N[n]:
        n += 1
    
    print(n)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
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

# 関数の呼び出し
P=callIsPrime(100010)

X=int(input())

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
x = int(input())
l = [i % 2 == 0 for i in range(100003)]
ans = 1
if x == 2:
    print(2)
    exit()
for i in range(3, 100003):
    if not l[i-1]:
        continue
    elif i >= x:
        print(i)
        break
    for j in range(1, 100003 // i + 1):
        l[i * j - 1] = False
else:
    print(100003)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        X = int(input())

        while not self.is_prime(X):
            X += 1

        print(X)

    def is_prime(self, n):
        for i in range(2, n + 1):
            if i * i > n:
                break
            if n % i == 0:
                return False
        return n != 1


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:
X = int(input())

primes = [2]
for i in range(3, 10 ** 5 + 1000, 2):
  chk = True
  for p in primes:
    if p * p > i :
      break
    if i % p == 0 : 
      chk = False
      break
  if chk == True : 
    primes.append(i)
    # print(primes)

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

Submission status: Accepted

Solution code:
import math

X = int(input())


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

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

print(X)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X = int(input())
p = 0
if X == 2 or X == 3:
  print(X)
else:
  while p == 0:
    q = 0
    for i in range(2, int(X**(1/2))+1):
      if X % i == 0:
        q += 1
        break
    if q == 0:
      p += 1
    else:
      X += 1
  print(X)

Submission status: Accepted

Solution code:
def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check 2p ~ (p-1)p (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return [i for i in range(ub+1) if prime[i]]

primes = sieve_of_eratosthenes(10**6)
X = int(input())
for i in range(X, 10**6):
    if i in primes:
        print(i)
        break

Submission status: Accepted

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

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

Submission status: Accepted

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

if __name__ == "__main__":
	x = int(input())
	for i in range(x, 2*x):
		if is_prime(i):
			print(i)
			break

Submission status: Accepted

Solution code:
n = int(input())
def get_sieve_of_eratosthenes(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
li = get_sieve_of_eratosthenes(10**5 + 3)
for i in li:
  if i >= n:
    print(i)
    exit()

Submission status: Accepted

Solution code:
import math
X=int(input())
if X==2:
  print(2)
else:
  for i in range(X, 10**5+10):
    if i%2==0:
      continue
    flag=True
    for j in range(3, int(math.sqrt(i))+10, 2):
      if i%j==0:
        flag=False
        break
    if flag:
      print(i)
      break

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):
    if(is_prime(x)):
        print(x)
        exit()
    else:
        x+=1

Submission status: Accepted

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

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

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

Submission status: Accepted

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

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


a = int(input())

while(True):
    if is_prime(a):
        print(a)
        break
    else:
        a+=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())
for i in range(x,10**6):
    if is_prime(i):
        ans = i
        break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math

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

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


if __name__ == "__main__":
    main()