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 sys
readline = sys.stdin.buffer.readline

import math
X = int(readline())


def is_prime(n) -> bool:
    if n == 2:
        return True

    for i in range(2, int(math.sqrt(n)) + 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:
x = int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
for i in range(x, x + 10000):
  f = factorization(i)
  if len(f) == 1 and f[0][1] == 1:
    print(i)
    exit()

Submission status: Accepted

Solution code:
x = int(input())

def get_primes(x):
    while True:
        for i in range(2, x):
            if x%i == 0:
                break
        else:
            yield x
        x += 1

i = get_primes(x)
print(next(i))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7

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

Submission status: Accepted

Solution code:
import math

x = int(input())

if x == 2:
    print(2)
    exit()

elif x%2 == 0:
    ans = x+1

else:
    ans = x

#2以外の素数は奇数であることに注意

while True:
    for i in range(3, int(math.sqrt(ans))+1, 2):
        if ans%i == 0:
            ans += 2
            break
    else:
        print(ans)
        exit()

Submission status: Accepted

Solution code:
pn = [2]
A = 100007

for i in range(3, A):
    chk = True
    for num in pn:
        if i % num == 0:
            chk = False
            break
    if chk:
        pn.append(i)

X = int(input())

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

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())
boole = True
while boole:
  if is_prime(x):
    print(x)
    boole = False
  else:
    x += 1

Submission status: Accepted

Solution code:

X = int(input())

while True:
    pf={}
    m=X
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    #print(i,pf)
    #print(len(list(pf)))

    if len(list(pf))==1 and list(pf.values())[0]==1:
        break
    else:
        X+=1

print(m)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    while not is_prime(X):
        X += 1

    print(X)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


def main():
    X = int(readline())

    P = prime_numbers(10 ** 6)
    ans = P[bisect_left(P, X)]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import io
import sys
import math

def solve(x):
    # implement process
    if x == 2:
        return 2
    if x%2 == 0:
        x+=1
    sosuu_lst = []
    i = 3
    while True:
        is_sosuu = True
        for a in sosuu_lst:
            if i % a == 0:
                is_sosuu = False
                break
        if is_sosuu:
            if i >= x:
                break
            sosuu_lst.append(i)
        i += 2

    return i

def main():
    # input
    x = int(input())
    
    # process
    ans = str( solve(x) )
    
    # output
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
99992
"""
_EXPECTED = """\
100003
"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Submission status: Accepted

Solution code:
import random
def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        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
X = int(input())
for i in range(X, 100004):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
import math


def is_prime(n):
    for i in range(2, int(math.sqrt(n))):
        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:
#素数判定
def Is_Prime(N):
    if N<=1:
        return False
    k=2
    while k*k<=N:
        if N%k==0:
            return False
        k+=1
    return True

#次の素数
def Next_Prime(N):
    """
    Nを上回る自然数のうち,最小の素数

    N:自然数
    """
    T=N+1
    while not Is_Prime(T):
        T+=1
    return T

#---------------------------------------------------------------------
N=int(input())
if Is_Prime(N):
    print(N)
else:
    print(Next_Prime(N))

Submission status: Accepted

Solution code:
x=int(input())
m=10**6

def segment_sieve(a,b):
    ass = []
    is_prime_small = [True] * (int(b**0.5)+1)
    is_prime = [True] * (b-a)
    for i in range(2,int(b**0.5)):
        if is_prime_small[i]:
            j = 2*i
            while j**2 < b:
                is_prime_small[j] = False
                j += i
            j = max(2*i,((a+i-1)//i)*i)
            while j < b:
                is_prime[j-a] = False
                j += i
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(a+i)
    if ass[0] == 1:
        del ass[0]
    return ass

print(min(segment_sieve(x,m)))

Submission status: Accepted

Solution code:
def is_prime(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 is_prime(p):
  p+=1
print(p)

Submission status: Accepted

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

def prime_list(X):
    N = X
    while True :
        for i in range(2,int(math.sqrt(N))+1):
            if N % i == 0:
                N = N + 1
                break
        else:
            break
    return N



print(prime_list(X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def prime(x):
    isprime = [True]*(x+1)
    isprime[0] = False
    isprime[1] = False
    for i in range(2,int(x**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i**2,x+1,i):
            isprime[j] = False
    return [i for i in range(x+1) if isprime[i]]

x = int(input())
lst = prime(10**6)
lst2 = [lst[i] for i in range(len(lst)) if lst[i] >= x ]
print(min(lst2))

Submission status: Accepted

Solution code:
from math import sqrt, ceil
def main():
    x = int(input())
    while True:
        for i1 in range(2, ceil(sqrt(x))):
            if x % i1 == 0:
                x += 1
                break
        else:
            break
    print(x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect
def main():
    maxa2 = 200000
    maxa2 = max(6, maxa2)  # maxa2が6未満だとエラーになる
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    prime_list = [i for i, b in enumerate(p) if b]

    x = int(input())
    if x in prime_list:
        print(x)
    else:
        xp = bisect(prime_list, x)
        r = prime_list[xp]
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
import numpy as np
#from collections import defaultdict
#import math
#from collections import deque

#input = sys.stdin.readline
#import decimal

def main():
    x = int(input())
    l = np.zeros(x*10)
    i = 2

    while True:
        if l[i] ==0:
            l[i::i] = 1
            if i>=x:
                print(i)
                exit()

        i +=1

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
a = int(input())

def factorization(n):
    arr = []
    tmp = n

    for i in range(2, int(n**0.5//1)+1):
        if tmp%i==0:
            cnt = 0
            while tmp%i==0:
                cnt+=1
                tmp//=i
            arr.append([i,cnt])
    if tmp!=1:
        arr.append([tmp,1])
    if arr==[]:
        arr.append([n,1])
    return arr

while True:
  arr = factorization(a)
  if (len(arr)==1) & (arr[0][1]==1):
    print(a)
    break
  a+=1

Submission status: Accepted

Solution code:
X = int(input())


def isPrime(x):
    i = 1
    while i ** 2 < x:
        i += 1
    i -= 1
    for j in range(2, i + 1):
        if x % j == 0:
            return False
    return True


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

Submission status: Accepted

Solution code:
X = int(input())

def bool_check(i):
    for j in range(2,i-1):
        if(i%j==0):
            return False
    return True
check=False
while check==False:
    check=bool_check(X)
    X+=1
print(X-1)

Submission status: Accepted

Solution code:
# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

X = int(input())


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


while not IsPrime(X):
    X += 1

print(X)

Submission status: Accepted

Solution code:
X = int(input())

def eratosthenes(n):
    search = set(range(2,n))
    result = set()
    while search:
        i = search.pop()
        result.add(i)
        mul = 2
        while mul * i < n:
            if mul * i in search:
                search.remove(mul * i)
            mul+=1
    return result

primeSet=eratosthenes(X-1)

while True:
    isPrime=True
    for p in primeSet:
        if X%p==0:
            isPrime=False
            continue
    if isPrime:
        break
    X+=1
    
print(X)

Submission status: Accepted

Solution code:
x=int(input())
m = 10**6
n=[0]*m
for i in range(2,m):
  if n[i] == 1: continue
  j = 2*i
  while j < m:
    n[j]=1
    j+=i
#print(n[:100])
for i in range(x,m):
  if n[i]==0:
    print(i)
    exit()

Submission status: Accepted

Solution code:
X = int(input())

num = X - 1
done = False
while not done:
    num += 1
    for i in range(2, num):
        if num % i == 0:
            break
    else:
        done = True

print(num)

Submission status: Accepted

Solution code:
x = int(input())
MAX = 10 ** 6
sieve = [True] * MAX
sieve[0] = False
sieve[1] = False
for i in range(2, MAX):
  if sieve[i] == False:
    continue
  for j in range(i*2, MAX, i):
    sieve[j] = False
#print(sieve[:30])
for j in range(x, MAX):
  if sieve[j]:
    print(j)
    exit(0)

Submission status: Accepted

Solution code:
X=int(input())
while True:
    for x in range(2,X):
        if X%x==0:
            break
        # 素数の場合、breakでfor文が抜けられないからelseが実行される
    else:
        print(X)
        break
    X+=1

Submission status: Accepted

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

Submission status: Accepted

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

def sosu(x):
    for i in range(2, math.floor(x**0.5)):
        if x%i ==0:
            return True

    return False

while sosu(x):
    x +=1

print(x)

Submission status: Accepted

Solution code:
x = int(input())

flag = [True]*(10**6+1)
flag[0] = flag[1] = False

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

Submission status: Accepted

Solution code:
x=int(input())

def sosu(t):
    cnt=0
    for i in range(2,t):
        if x%i==0:
            cnt+=1
            break
    if cnt==0:
        return True

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

def sieve(n=10**5 + 9):
    # srn = int(n ** 0.5) + 1
    f = [False] * (n + 1)
    res = []
    for i in range(2, n+1):
        if f[i]:
            continue
        res.append(i)
        for j in range(2 * i, n + 1, i):
            f[j] = True
    return res

X = int(input())
pn = sieve()
idx = bisect_left(pn, X)
print(pn[idx])

Submission status: Accepted

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

def sosu(num):
  cnt = 0
  for i in range(2, int(math.sqrt(num))+1):
    if num % i == 0:
      cnt += 1
      break;
  if cnt == 0:
    return True
  
while True:
  if sosu(X):
    print(X)
    break;
  else:
    X += 1