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())
if x <= 3:
  n = x
elif x == 4:
  n = 5
else:
  n = x
  j = 0
  while j == 0:
    a = int(n/2) + 1
    i = 2
    while i < a:
      if i == a-1:
        j = 1
        i = a
      elif n % i != 0:
        i += 1
      else:
        i = a
        n += 1
print(n)

Submission status: Accepted

Solution code:
X = int(input())
while X != 'prime':
    for i in range(2,X):
        if X%i == 0:
            break
    else:
        break
    X+=1

            
print(X)

Submission status: Accepted

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

import sys
import math
import itertools

debug = False

def log(text):
    if debug:
        print(text)


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # error?
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())

    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    x = [int(e) for e in lines[0].split(" ")][0]

    return (x, )


def solve(x):

    primes = set()

    def is_prime(n):
        
        if n in primes:
            return True

        if n == 1:
            return False

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

        return True

    y = x
    result = 0
    while True:
        if is_prime(y):
            result = y
            break
        else:
            y = y + 1

    return result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

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 = int(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

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

print(x)

Submission status: Accepted

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

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

while True:
    if isPrime(X):
        print(X)
        sys.exit()
    else:
        X += 1

Submission status: Accepted

Solution code:
import math
X = int(input())
if X ==2:
    print(2)
    exit()
elif X%2 == 0:
    X += 1
X -= 2
while True:
    X +=2
    for i in range(2,math.ceil(X**0.5)):
        if X%i ==0:
            break
    else:
        print(X)
        exit()

Submission status: Accepted

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

    return True
  
temp = int(input())
while not isPrime(temp):
  temp += 1
print(temp)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc149/tasks/abc149_c
import math


def is_prime(x):
    for i in range(2, math.floor(math.sqrt(x))):
        if x % i == 0:
            return False
    return True


def main():
    n = int(input())
    for i in range(n, 100004):
        if is_prime(i):
            print(i)
            break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
X = int(input())


def isPrime(n):
    if n == 0 or n == 1:
        return False
    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 n != 1


for i in range(X*2+1):
    num = X + i
    if isPrime(num):
        break

print(num)

Submission status: Accepted

Solution code:
# import numpy as np
import math
import sys
input = sys.stdin.readline

X = int(input())

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

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

list = segment_sieve(X,100004)
res = list[0]

print(res)

Submission status: Accepted

Solution code:
X = int(input())
ans = 0
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

for i in range(X, 100004, 1):
  if is_prime(i):
    ans = i
    break

print(ans)

Submission status: Accepted

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

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 = int(math.sqrt(n)) +1
    for p in range(3, m, 2): 
        if n % p == 0:
            return False
    return True

def nextprime(n):
    if n < 2:
        return 2
    if n < 7:
        return {2: 3, 3: 5, 4: 5, 5: 7, 6: 7}[n]
    nn = 6*(n//6)
    if nn == n:
        n += 1
        if isprime(n):
            return n
        n += 4
    elif n - nn == 5:
        n += 2
        if isprime(n):
            return n
        n += 4
    else:
        n = nn + 5
    while 1:
        if isprime(n):
            return n
        n += 2
        if isprime(n):
            return n
        n += 4

print(X if isprime(X) else nextprime(X))

Submission status: Accepted

Solution code:
X = int(input())
flag = 0

while 1:
    flag = 0
    for i in range(2,X):
        if(X % i==0):
            flag = 1
            
    if flag ==0:
        print("{}".format(X))
        break
    
    else:
        X+=1

Submission status: Accepted

Solution code:
import math
import sys

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, 10**5 + 4):
    if is_prime(i):
        print(i)
        sys.exit()

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 True:
    if is_prime(X):
        print(X)
        break
    else:
        X = X + 1

Submission status: Accepted

Solution code:
import bisect

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 is_prime, table

a, b = sieve(10**5+3)
X = int(input())

idx = bisect.bisect_left(b, X)
if b[idx] == X:
  ans = X
else:
  ans = b[idx]

print(ans)

Submission status: Accepted

Solution code:
import random

def func(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())
while x == x:
  if func(x) == True:
    print(x)
    break
  x += 1

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

x = int(input())

if (x == 2):
  print(x)
else:
  while((is_prime(x)!=True)):
    x += 1
  print(x)

Submission status: Accepted

Solution code:
import random
num = int(input()) - 1

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)

result = False
while(result == False):
    num += 1
    result = is_prime(num)

print(num)

Submission status: Accepted

Solution code:
def check_prime(num):
  for i in range(2,num):
    if (x % i == 0):
      return False
      break
  else: 
    return True
 
if __name__ == "__main__":
  x = int(input())
  flag = True
  while flag: 
    if (check_prime(x)):
      print(x)
      flag = False
    else: 
      x = x + 1

Submission status: Accepted

Solution code:
x = int(input())
a = 2

while True:
    while a <= int(x**0.5//1):
        if x%a == 0: break
        a += 1
    else:
        ans = x
        break
    x += 1
    a = 2

print(ans)

Submission status: Accepted

Solution code:

import math

X = int(input())

ans = 0
while ans == 0:
    ans = X
    for i in range(2, int(math.sqrt(X)) + 1 ):
        if X % i == 0:
            ans = 0
            break
    
    if ans == X:
        break

    X = X + 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import math

def get_primenumber(number):
    prime_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 max(prime_list)

    
a = int(input())
r_before = get_primenumber(a)
s_after = get_primenumber(a)
count = a + 1
if a != r_before:
    while r_before == s_after:
        s_after = get_primenumber(count)
        count += 1
    
print(s_after)

Submission status: Accepted

Solution code:
import math
x = int(input())-1
ans = 0
while ans==0:
    x+=1
    n = int(math.sqrt(x))+1
    for i in range(2,n):
        if x%i ==0:
            ans -= 1
            break
    ans+=1
print(x)

Submission status: Accepted

Solution code:
x = int(input())

not_found = True
ans = None

if x >= 2 and x <= 10**5:
    for i in range(2, x):
        if (x % i) == 0:
            break
    else:
        ans = x

    x += 1

    while(ans == None):
        for i in range(2, x):
            if (x % i) == 0:
                x += 1
                break
        else:
            ans = x


    print(ans)

Submission status: Accepted

Solution code:
import random

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

a = int(input())

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

print(a)

Submission status: Accepted

Solution code:
x=int(input())
ans=x
for i in range(100000):
    flag=0
    for j in range(2,ans-1):
        if ans%j==0:flag=1
    if flag==0:
        break
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input().strip())

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

    if is_prime(N):
        print(N)
        break

    else:
        N += 1

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


def main(x):
    while True:
        if is_prime3(x):
            return x
        x += 1

print(main(X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a=int(input())
def Isprime(n):
    if n==2:
        return 1
    for i in range(n-2):
        if n%(i+2)==0:
            return 0
    return 1
k=0
while k<a:
    if Isprime(a+k)==1:
        print(a+k)
        break
    else:
        k+=1

Submission status: Accepted

Solution code:
import math
X = int(input())
if X ==2:
    print(2)
    exit()
elif X%2 == 0:
    X += 1
j = 0
X -= 2
while j == 0:
    X +=2
    for i in range(2,math.ceil(X**0.5)):
        if X%i ==0:
            break
    else:
        print(X)
        exit()

Submission status: Accepted

Solution code:
import math

X=int(input())
rt=int(math.sqrt(X))

def prime(A):
  pn=[2]
  for L in range(3,A+1,2):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)
  return pn

pm_list=prime(rt)


if X in pm_list:
  print(X)
else:
  get_pri=False
  N=X
  
  while get_pri==False:
    judge=True
    for i in pm_list:
    
      if N%i==0:
        judge=False
        continue
    if judge==True:
      get_pri=True
      print(N)
    N+=1

Submission status: Accepted

Solution code:
def eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    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]

N = int(input())
N2 = N + 336

A = eratosthenes(N2)

ans = 0
for i in range(len(A)):
    if A[i] == N:
        ans = A[i]
        break
    elif A[i] < N and A[i+1] > N:
        ans = A[i+1]
        break
print(ans)

Submission status: Accepted

Solution code:
import math
a=int(input())
for i in range(100000):
 for k in range(2, int(math.sqrt(i+a)) + 1):
        if (i+a) % k == 0:
         break
 else:
  print(i+a)
  break
 continue

Submission status: Accepted

Solution code:
x=int(input())
flag=True
k=-1
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 True

    return False
  
while flag:
  k+=1
  flag=is_prime(x+k)
print(x+k)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
X = int(input())
ans = 0
pn = [2]
flag = 0
for i in range(3,100005):
  for k in pn:
    if i%k == 0:
      flag = 0
      break
    else:
      flag = 1
  if flag == 1:
    pn.append(i)
for i in range(len(pn)-1):
  if pn[i] == X:
    ans = pn[i]
  elif pn[i] < X < pn[i+1]:
    ans = pn[i+1]
print(ans)

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

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

Submission status: Accepted

Solution code:
import math

X = int(input())
while True:
  flg = True
  for i in range(2, int(math.sqrt(X)) + 1):
    if X % i == 0:
      X += 1
      flg = False
      break
  if flg:
    print(X)
    exit()

Submission status: Accepted

Solution code:
x = int(input())

cad = x

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
    
while True:
    
    flag = is_prime(cad)
    if flag:
        print(cad)
        break
    cad += 1

Submission status: Accepted

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

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

def sosu(x):
    arr = factorization(x)
    if len(arr) == 1 and arr[0][0] == x:
        return True
    else:
        return False

def solve(X: int):
    ans = 100003
    for i in range(X, 10**5 + 1):
        #if i % 2 == 0 and X != 2:
        #    continue
        if sosu(i):
            ans = i
            break

    print(ans)

# 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):
    for i in range(2, int(math.sqrt(n))):
        if n % i == 0:
            return 0
    return 1


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

    for i in range(X, 100003+1):
        if is_prime(i):
            print(i)
            break
        else:
            continue


if __name__ == '__main__':
    main()