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:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

def prime_factorize(n, unique=False):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    if unique:
        return set(fct)
    else:
        return fct

x = int(input())
for i in range(x, x+100):
    ret = prime_factorize(i)
    if len(ret) == 1:
        print(ret[0])
        exit()

Submission status: Accepted

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

Submission status: Accepted

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

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

def main():
    x = int(input())
    for i in range(x, 1000000):
        if isPrime(i):
            print(i)
            return

main()

Submission status: Accepted

Solution code:
x = int(input())


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


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

Submission status: Accepted

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

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


# 素数判定の関数
def check(n):
  ans = True
  for i in range(2,int(n**0.5)):
    if n % i == 0:
      ans = False
      break

  return ans


flg = True
cnt = 0
while flg:
  _ = X+cnt
  ck = check(_)
  if ck:
    flg = False
    ans = _
  
  cnt += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	X = inputInt()

	for i in range(X, 10000000000):
		if is_prime(i):
			print(i)
			sys.exit()

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

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
X = int(input())
def get_primes(n):
  numbers = [i for i in range(2, n+1)]
  primes = []
  while True:
    k = numbers[0]
    primes.append(k)
    numbers = [i for i in numbers if i % k != 0]
    if k**2 > n:
      return primes + numbers
l = get_primes(X)
if l[-1] == X:
  print(X)
else:
  x = X + 1
  while True:
    d = True
    for p in l:
      if x % p == 0:
        d = False
        break
    if d == False:
      x += 1
    else:
      break
  print(x)

Submission status: Accepted

Solution code:
import math

def IsP(n):
    s = int(math.ceil(math.sqrt(x)))
    if(n<=1):
        return 0
    elif(n==2):
        return 1
    else:
        for i in range(2,s+1):
            if(n%i == 0):
                return 0
        return 1

x = int(input())

while(IsP(x)==0):
    x +=1
print(x)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

ps = primes(10**5+100)

i = bisect_left(ps,x)
print(ps[i])

Submission status: Accepted

Solution code:
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True

X = int(input())
flg = True
ans = 0
while flg:
  if isPrime(X):
    flg = False
    ans = X
  X +=1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

X = int(input())

N = 10 ** 6 + 10
# N = int(input())
def primes(n):
    import math
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 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]]

prime_lst = primes(N)

tmp = bisect_left(prime_lst, X)
print (prime_lst[tmp])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache
import heapq

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7

def main():
    X = cin.int()
    while not Math.isPrime(X):
        X +=1
    print(X)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
X = int(input())

ans = 0

while(True):
  count = 0
  for i in range(1, X+1):
    if i == 1 or i == X:
      continue

    if X % i == 0:
      count += 1

  if count == 0:
    ans = X
    break
  else:
    X += 1

print(ans)

Submission status: Accepted

Solution code:
import math

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

n = int(input())

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def p_prime(n): 
    prime = [2]
    for i in range(3,n+1):
        flag = 0
        for j in prime:
            if i%j == 0:
                flag = 1
                break
            if i**0.5 < j:
                break
        if flag == 0:
            prime.append(i)
    return prime

prime = p_prime(10**5+1000)

X = int(input())

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

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
 
def main():
    X = int(input())
    while True:
        result = is_prime(X)
        if result:
            print(X)
            exit()
        X +=1
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

    return True

def main():
    n = int(input())
    while True:
        result = is_prime(n)
        if result:
            print(n)
            exit()
        n += 1

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

X = int(input())

def checkprime(N):
    for i in range(2,int(np.sqrt(N))+1):
        if N%i == 0:
            return False
    return True

while True:
    if checkprime(X):
        print(X)
        exit()
    X += 1

Submission status: Accepted

Solution code:
def func(x):
  if x==2:
    return True
  
  for i in range(2,x):
    if i*i > x:
      return True
    elif x%i == 0:
      return False
    else:
      continue

X=int(input())

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

Submission status: Accepted

Solution code:
import sys
import math
x = int(sys.stdin.readline())
divs = 2
answer = 0
if x == 2:
  answer=2

while True:
  if divs >= int(math.sqrt(x)):
    answer = x
    break
  if x % divs == 0:
    x += 1
    divs = 2
  else:
    divs += 1
  
print(answer)

Submission status: Accepted

Solution code:
import math

X = int(input())

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

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    for i in range(3, math.ceil(math.sqrt(n)), 2):
        if n % i == 0:
            return False

    return True
    
while not is_prime(X):
    X += 1

print(X)

Submission status: Accepted

Solution code:
X = int(input())

work = list(range(2,X))
P = [True] * (X+1)
P[0] = False
P[1] = False

for a in work:
  if not P[a]:
    continue
  for i in range(a+a,X,a):
    P[i] = False
  #print(a,P)
#print(P)

for N in range(X,X+1000):
  flg = True
  for i in range(2,len(P)-1):
    if P[i] and N%i == 0:
      flg = False
      break
  
  if flg:
    print(N)
    exit(0)

Submission status: Accepted

Solution code:
x = int(input())
primes = [True for _ in range(2*x)]
for i in range(2,len(primes)):
    if primes[i]:
        index = 2
        while i * index < len(primes):
            primes[i * index] = False
            index+=1

for num in range(2,len(primes)):
    if primes[num] and num >= x:
        print(num)
        break

Submission status: Accepted

Solution code:
import numpy as np

X=int(input())
n=0
count=0
ans=0

for i in range(X,10**6):
  n=np.sqrt(i)
  n=int(n)
  count=0
  for j in range(2,n+1):
    if i%j==0:
      break
    else:
      count+=1
  if count==n-1:
    ans=i
    break
  
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

def isprime(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 = ni()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

a = int(input())
while prime(a) == False:
  a += 1
    
print(a)

Submission status: Accepted

Solution code:
import math

x = int(input())

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


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

print(x)

Submission status: Accepted

Solution code:
x = int(input())

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

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

Submission status: Accepted

Solution code:
from math import sqrt

def IsPrime(n: int) -> bool:
    cnt = 2
    while cnt * cnt <= n:
        if n % cnt == 0:
            return False
        else:
            cnt += 1
    return True

def main():
    x = int(input())
    while True:
        if (IsPrime(x)):
            print(x)
            exit()
        else:
            x += 1

if __name__ == '__main__':
    main()