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


def sosuu(val):
    if val <= 3:
        return True
    else:
        for i in range(2, val):
            if val % i == 0:
                return False
        else:
            return True

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

print(X)

Submission status: Accepted

Solution code:
n = int(input())

def getpr(x):
    check = True
    while True:
        for i in range(2,int(x**0.5)+1):
            if x%i == 0:
                check = False
        if check:
            return x
        else:
            check = True
            x += 1

print(getpr(n))

Submission status: Accepted

Solution code:
from sys import stdin
import math
n = int(stdin.readline().rstrip())
m = n
k = 0
t = 0
while k == 0:
    for i in range(int(math.sqrt(m))+1):
        if i >= 2:
            if m % i == 0:
                t = 1
    if t == 0:
        k = 1
        l = m
    t = 0        
    m += 1
print(l)

Submission status: Accepted

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

if N==2:
  print(2)
else:
  if N%2==0:
    N+=1
  while len(prime_factorize(N))!=1:
    N+=2
  print(N)

Submission status: Accepted

Solution code:
import math


def main():
    x = int(input())

    primes = []
    i = 2
    while True:
        if len(primes) == 0:
            primes.append(i)
        max_val = int(math.sqrt(i))
        is_prime = True
        for p in primes:
            if p > max_val:
                break
            if i % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
            if x <= i:
                print(i)
                return
        i += 1


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
X = int(input())
import math
array = [2]
for i in range(3, 10**10, 2):
    if X == 2:
        break
    sosu = True
    for n in range(len(array)):
        if array[n] > math.sqrt(i):
            break
        if i % array[n] == 0:
            # これまで取得した素数で割る
            sosu = False
            break
    if sosu:
        array.append(i)
        if i >= X:
            break
print(array[-1])

Submission status: Accepted

Solution code:
import math
x=int(input())
ok=0
ans=0
if x==2:
    print(x)
else:
    if x%2==0: #偶数なら一個上の奇数から
        x+=1
    while ok==0:
        now=x
        sosu=0 #素数だったら、０のまま
        for i in range(2,int(math.sqrt(now))+1):
            if i%2==0:
                continue
            else:
                if now%i==0: #素数じゃない
                    sosu=1
                    break
        x+=2
        if sosu==0:
            ok=1
            ans=now
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

x = int(input())

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    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
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table

sosu_table = sieve(100000)
sosu_table.append(100003)

sosu_table = np.array(sosu_table)

print(sosu_table[x<=sosu_table][0])

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

Submission status: Accepted

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

def is_prime(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
for i in range(x,10**6):
  if is_prime(i)==True:
    print(i)
    exit()

Submission status: Accepted

Solution code:
import math
 
number = 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

for i in range(10000000):
    if is_prime(number):
        print(number)
        break
    else:
        number += 1

Submission status: Accepted

Solution code:
x=int(input())
import numpy as np
root=int(np.sqrt(x))
for i in range(x,2*x):
  c=0
  for j in range(2,root):
    if i % j == 0:
      c=1
      break
    else:
      continue
  if c==0:
    print(i)
    exit()

Submission status: Accepted

Solution code:
import sys
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())

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

for i in range(x, 10**5+4):
    if i % 2 == 1 and is_prime(i):
        print(i)
        sys.exit()

Submission status: Accepted

Solution code:
import math

def trial(k):
    factor = []
    m = int(math.sqrt(k)) + 1
    for i in range(2,m):
        while k % i == 0:
            k = k // i
            factor.append(i)
    if not factor:
        return [1,k]
    else:
        factor.append(k)
        factor.append(1)
        return factor

def isPrime(x):
    return (len(trial(x)) == 2)

x = int(input())

while not isPrime(x):
    x += 1

print(x)

Submission status: Accepted

Solution code:
n = int(input())


def isprime(x):
    if x == 2:
        return True
    if x < 2 or x % 2 == 0:
        return False
    i = 3
    while i <= x ** 0.5:
        if x % i == 0:
            return False
        i += 2
    return True


a = n
while 1:

    if isprime(a):
        print(a)
        break
    # print(a)
    a += 1

Submission status: Accepted

Solution code:
X=int(input())
flag = True
if X == 2:
    print(X)
else:
    while flag:
        i = 2
        while i<X:
            if X%i == 0:
                break
            if i == X-1:
                print(X)
                flag = False
                break
            i = i+1
        X = X+1

Submission status: Accepted

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

x = int(input())
def isPrime(x):
    for p in range(2, int(x**0.5)+1):
        if x % p == 0:
            return False
    return True
while 1:
    if isPrime(x)==True:
        print(x)
        exit()
    else:
        x += 1

Submission status: Accepted

Solution code:
x=int(input())

def pr(n):
    for p in range(2,n):
        if n%p==0:
            return pr(n+1)
    return n
print(pr(x))

Submission status: Accepted

Solution code:
n=int(input())
if(n==2):
  print(n)
  exit()
if(n==3):
  print(n)
  exit()
for i in range(10000):
  hoge=n+i
  ans=0
  for j in range(int(hoge**0.5)):
    if(hoge%(j+2)!=0):
      ans+=1
  if(ans==int(hoge**0.5)):
    print(hoge)
    exit()

Submission status: Accepted

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



#test
while True:
     if is_prime3(n):
         break
     n+=1
print(n)

Submission status: Accepted

Solution code:
X = int(input())

def is_prime(x):
    if x < 4:
        return True
    
    if (x % 2 == 0) or (x % 3 == 0):
        return False
  
    for i in range(5, int(x**0.5)+1):
        if x % i == 0:
            return False
    
    return True
  
ans = None
while True:
    if is_prime(X):
        print(X)
        break
    else:
        X += 1

Submission status: Accepted

Solution code:
X=input()
max_num=10**6
A=[ 0 for _ in range(max_num+1) ]
A[1]=1

t_sqrt=int(max_num**0.5)

for n in range(2,t_sqrt+2):
    for i in range(n*2,max_num+1,+n):
        A[i]=1

for i in range(X,max_num+1):
    if A[i]==0:
        print i
        quit()

Submission status: Accepted

Solution code:
X=int(input())

import math
import bisect

candidate = [i for i in range(2, 100004)] 
prime = []
limit = math.sqrt(100004) + 1 

while True:
    p = min(candidate)
    if limit <= p:
        prime.extend(candidate)
        break
    prime.append(p)
    candidate = [i for i in candidate if i % p != 0]

a=bisect.bisect_left(prime,X)
print(prime[a])

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 True
  
INF = 10 ** 9
  
judge = is_prime(X)

if judge == True:
  print(X)
else:
  if X % 2 == 0:
    X = X + 1
    for i in range(X,INF,2):
      judge = is_prime(i)
      if judge == True:
        print(i)
        break
  else:
    for i in range(X,INF,2):
      judge = is_prime(i)
      if judge == True:
        print(i)
        break

Submission status: Accepted

Solution code:
def isPrime(x):
  if x < 2:
    return False
  for i in range(2,x):
    if x%i == 0:
      return False
  return True

num = int(input())

for i in range(num,100004):
  if isPrime(i):
    print(i)
    break

Submission status: Accepted

Solution code:
# そのまま入力文字列の入力
x = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return set(divisors)

def is_prime(n):
    yakusu_set = make_divisors(n)
    return (n in yakusu_set) and len(yakusu_set) == 2


yakusu_set = make_divisors(x)
yakusu_set.remove(1)

if x in yakusu_set and len(yakusu_set) == 1:
    print(x)
else:
    next_num = x
    while True:
        next_num += 1
        if is_prime(next_num):
            print(next_num)
            break

Submission status: Accepted

Solution code:
def prime(n):
    p = True
    for i in range(2, round(n**0.5)+1):
        if n % i == 0:
            p= False
            break
    return p

x = int(input())

if x == 2 or x == 3:
    print(x)
elif x == 4 or x == 5:
    print(5)
else:
    p = prime(x)
    while not p:
        x = x + 1
        p = prime(x)
    print(x)

Submission status: Accepted

Solution code:
import math

def is_prime(n):
    if n == 2:
        return True

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

X = int(input())

while 2 <= X <= 100010:
    if is_prime(X) == True:
        print(X)
        break
    X += 1

Submission status: Accepted

Solution code:
x = int(input())
c = 0
ans = 2
for i in range(1000):
    for j in range(int(x / 2)):
        if x == 2:
            c = 1
            break
        elif (x + i) % (j + 2) == 0:
            c = 1
            break
    if c == 0:
        ans = x + i
        break
    else:
        c = 0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def prime_list(n):
  prime = [2]
  limit = int(n ** 0.5)
  data = [i + 1 for i in range(2, n, 2)]
  while True:
    p = data[0]
    if limit <= p:
      return prime + data
    prime.append(p)
    data = [e for e in data if e % p != 0]
    
p = prime_list(101000)
#print(p[:10])

for pp in p:
  if pp >= N:
    print(pp)
    exit()

Submission status: Accepted

Solution code:
X=int(input())

def judge(x):
   flag=True
   for i in range(2,x):
      if x%i==0:
         flag=False
         break
   return flag

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

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

# 自然数m以下の素数を返す
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]]

def prime_numbers_under(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1

    return primes

# 自然数m以上の素数を返す
def prime_numbers_over(m):
    # 素数を保持するset
    # primes = set()
    global p

    if m in p:
        return m

    while True:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(m % i != 0 for i in p):
            return m
        m += 1

# p = prime_numbers_under(x)
p = primes(x)

print(prime_numbers_over(x))

Submission status: Accepted

Solution code:
# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/
#
# lang: Python3 (3.4.3)

import math
import statistics
import numpy as np
import queue

def eratosthenes(n):
  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]
  return prime

x = int(input())
while True:
  ary = eratosthenes(x)
  if ary[-1] == x:
    break
  else:
    x += 1
print(x)

Submission status: Accepted

Solution code:
import math
 
serach_number = 10 ** 5 + 4

def sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []
 
    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)
 
 
        i = 0
 
        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1
 
    return prime_list
 
ps = sieve_of_eratosthenes(serach_number)

x = int(input())

while x < 10 ** 5 + 4:
  if x in ps:
    print(x)
    break
  else:
    x += 1

Submission status: Accepted

Solution code:
import math

a = int(input())
while True:
    for x in range(2, a):
        if a % x == 0:
            break

    else:
        print(a)
        quit()
    a += 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
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True
for i in range(X,100010):
	if(isPrime(i)):
		print(i)
		exit()

Submission status: Accepted

Solution code:
x=int(input())
l=[]
if x==2:
    print(2)
    exit()
for i in range(2,x):
    for j in l:
        if i%j==0:break
    else:
        l.append(i)
if x%2==0:x+=1
while True:
    for i in l:
        if x%i==0:
            x+=2
            break
    else:
        break
print(x)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def main():
  x=I()
  l=primes(x+10000)

  for i,y in enumerate(l):
    if x<=y:
      return l[i]

# main()
print(main())

Submission status: Accepted

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

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

print(x)

Submission status: Accepted

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

i = 0
while i < 1:
  sq = int(math.sqrt(X) // 1)
  j = 0
  for k in range(1, sq+1, 1):
    if X % k != 0:
      j += 1
  else:
    if j == sq-1:
      print(X)
      break
    else:
      j = 0
      X += 1

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


def sosu(x):
    for i in range(2, int(sqrt(x)+1)):
        if x % i == 0:
            return False
    return True


mod = 1000000007
inf = float('INF')


def A():
    S, T= input().split()
    
    
    print(T+S)

    
    return

# B


def B():
    A,B,K= LI()
    temp=A-K
    if temp>=0:
        print(temp,B)
        return
    B=B+temp
    if B<=0:
        print(0,0)
        return
    else:
        print(0,B)
    
    
    

   
    return

# C


def true():
    S = input()
    S = S[:-1]

    tmp = 0
    for x in range(1 << (len(S)-1)):
        func = S[-1]
        for i in range(len(S)-1):
            if(x & (1 << i)):
                tmp += int(func)
                func = S[-2-i]
            else:
                func = S[-2-i]+func
        tmp += int(func)
    print(tmp)

    return


def flagcounter(x):
    if (x == 0):
        return 0
    return flagcounter(x >> 1)+(x & 1)


def C():
    X=II()
    if X==2:
        print(2)
        return
    while(1):
        if sosu(X):
            print(X)
            return
        X+=1

   
    return


# D


def D():

    N, K = LI()
    A = LI()
    MAX = sum(A)
    if MAX < K:
        print(0)
        return
    Temp = MAX
    ans = 1
    for i in range(N):
        Temp = Temp-A[i]
        if (Temp >= K):
            ans += 1
        else:
            T = Temp+A[i]
            break
    Temp = T
    ckeep = N
    for k in range(N):
        c = N-1
        i -= 1
        Temp = T

        for j in range(N):
            Temp = Temp-A[c]
            if (Temp >= K ):
                ans += 1
            
            elif(c < ckeep and i>=0):
                ans += i
                ckeep = c
                break
            else:
                ckeep = c
                break
            c -= 1
        if i < 0:
            break
        T = T+A[i]
    print(ans)

    return

# E


def E():
    N, K = LI()
    A = LI()
    F = LI()
    A.sort(reverse=True)
    F.sort()
    cost = []
    for i in range(len(N)):
        cost.append(A[i]*F[i])

    a = F[cost.index(max(cost))]

    return

# F


def F():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    N = len(S)

    pass


# Solve
if __name__ == '__main__':

    C()

Submission status: Accepted

Solution code:
x = int(input())
flag = False
while not flag:
    n = x
    cnt = 0
    for i in range(2, int(n**0.5+1)):
        if n % i == 0:
            cnt += 1
    if cnt == 0:
        print(n)
        flag = True
    else:
        x += 1

Submission status: Accepted

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

X = int(input())

count_n = 0
count_i = 0

while count_n < 1:
    for i in range(1,X):
        if X % i == 0:
            count_i += 1

    if count_i == 1:
        count_n += 1
    
    count_i = 0

    X += 1

print(X-1)

Submission status: Accepted

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
N = int(input())
for p in primes(10**5+100):
    if N<=p:
        print(p)
        break

Submission status: Accepted

Solution code:
import sys
x=int(input())
if x==2:
  print(2)
  sys.exit()
for i in range(x,10**5+4):
  for j in range(2,round(i**0.5)+1):
    if i%j==0:
      break
    if j==round(i**0.5) and i%j!=0:
      print(i)
      sys.exit()