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:
def is_prime(n):
    if n == 1:
        return False

    i = 2
    while True:
        if i ** 2 >= n:
            return True
        if n % i == 0:
            return False
        i += 1

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

Submission status: Accepted

Solution code:
import math
def primecheck(x):

    for i in range(2,math.ceil(x*(1/2))):
        if x % i == 0:
            return False
            break 
    return True



x = int(input())
for i in range(x,10**6):
    if primecheck(i):
        break
print(i)

Submission status: Accepted

Solution code:
import math
x = int(input())
limit = 10**5
i = x
while True:
  for j in range(2, int(math.sqrt(i))+1):
    if (i%j)==0:
      break
  else:
    # すべてのjで割り切れなかった場合
    print(i)
    break
  i += 1

Submission status: Accepted

Solution code:
import math
from itertools import product
x = int(input())
limit = 10**5
sosu = -1
flag = 1
i = x
while True:
  for j in range(2, int(math.sqrt(i))+1):
    if (i%j)==0:
      flag = 0
      break
  if flag:
    sosu = i
    break
  else:
    i += 1
    flag = 1
print(sosu)

Submission status: Accepted

Solution code:
def get_sieve_of_eratosthenes_new(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]

x=int(input())

A=get_sieve_of_eratosthenes_new(10**5+1000)
for i in range(0,len(A)):
    if A[i]>=x:
        print(A[i])
        break

Submission status: Accepted

Solution code:
x = int(input())
for i in range(x,10**5 +4):
    for p in range(2, int(x**(1/2)+1)):
        if i%p == 0 :
            break
    else:
        print(i)
        break

Submission status: Accepted

Solution code:
N = int(input())
LENGTH = 100010
array = [1]*LENGTH
array[0], array[1] = 0, 0
for i in range(320):
    if array[i] == 1:
        cnt = 2
        while i * cnt <= LENGTH - 1:
            array[i*cnt] = 0
            cnt += 1

for i in range(N, LENGTH):
    if array[i] == 1:
        print(i)
        exit()

Submission status: Accepted

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

while 1:
    for i in range(x-1,1,-1):

        if x % i == 0:
            flag = 1
            break

    if flag == 0:
        print(x)
        break
    flag = 0
    x += 1

Submission status: Accepted

Solution code:
x = int(input())

while True:
    c = 0
    for i in range(2, x+1):
        if x % i == 0:
            c += 1
    if c == 1:
        print(x)
        exit()
    else:
        x += 1

Submission status: Accepted

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

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

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

print(x)

Submission status: Accepted

Solution code:
X = int(input())

def soi(n,l):
  if n ==1:
    l.append(1)    
    return l
  else:
    for i in range(2,n+1):
      if n%i == 0:
        l.append(i)
        break
    soi(n//i,l)
    return l
  

for i in range(X,10**9,1):
  l = soi(i,[])
  #print(l)
  if (len(l)==2):
    print(i)
    break

Submission status: Accepted

Solution code:
N = int(input())

def isPrime(n):
  for i in range(2,n-1):
    if n%i == 0:
      return False
  return True
i= N
while(True):
  if isPrime(i):
    print(i)
    break
  i+=1

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import math
x=int(input())
flag=True
if x==2:
    print(x)
else:
    while flag:
        i=2
        f=True
        while i<math.sqrt(x) and f:
            if x%i==0:
                f=False
            i+=1
        if f==True:
            print(x)
            flag=False
        else:
            x+=1

Submission status: Accepted

Solution code:
import math
x=int(input())
flag=True
if x==2:
    print(x)
else:
    while flag:
        i=2
        f=True
        while i<x and f:
            if x%i==0:
                f=False
            i+=1
        if f==True:
            print(x)
            flag=False
        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())

while True:
    if is_prime(x):
        print(x)
        break
    x += 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
  
i = X
cnt = 0
flg = is_prime3(i)
if flg == False:
    while flg==False:
        i += 1
        cnt = i
        flg = is_prime3(i)
    print(cnt)
else:
    print(i)

Submission status: Accepted

Solution code:
X = int(input())

def is_prime(num):
    for i in range(2, num):
        if X % i == 0:
            return False
        if X == 1:
            return False
    return True

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

Submission status: Accepted

Solution code:
n = int(input())

flag = False
while flag==False:
    for i in reversed(range(1,n//2+1)):
            
        if i==1:
            print(n)
            flag=True
            break
            
        if n%i==0:
            break
            
    n += 1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

X = int(input())

a=0
if X==2 or X==3:
  a=1
while a<1:
  for i in range(2,int(np.sqrt(X))+1):
    a=1
    if X%i==0:#素数でない
      a=0
      break
    else:#素数かも
      pass
  if a==0:
    X+=1
print(X)

Submission status: Accepted

Solution code:
def main():
    s = int(input())
    for i in range(s,s+100):
        x = 2
        is_prime = True
        while x * x <= i:
            if i % x == 0:
                is_prime = False
                break
            x += 1
        if is_prime:
            print(i)
            return

main()

Submission status: Accepted

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

for i in range(x, 100004):
    flag = True
    for j in range(2, math.floor(math.sqrt(i))+1):
        if i % j == 0:
            flag = False
            break
    if flag:
        print(i)
        exit(0)

Submission status: Accepted

Solution code:
import math
x = int(input())
for i in range(x, x * 2):
    flag = True
    for j in range(2, math.floor(math.sqrt(x))+1):
        if i % j == 0:
            flag = False
            break
    if flag:
        print(i)
        exit(0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Feb  2 17:39:27 2020

@author: H_Hoshigi
"""

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

if __name__ == "__main__":
    X = int(input())
    p = X
    while not(is_prime(p)):
        p += 1
    print(p)

Submission status: Accepted

Solution code:
import math

num = int(input())
prime_found = False

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

Submission status: Accepted

Solution code:
def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    for i in range(3,int(x**0.5)+1, 2):
        if x%i == 0 :
             return False
    return True

x = int(input())
for i in range(x, 100003):
    if is_prime(i):
        print(i)
        break
else:
    print(100003)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Feb  2 17:14:11 2020

@author: masat
"""
import math

X = int(input())
i = X

if i == 2:
    pass
else:
    i_is_prime = True
    while True:
        for k in range(2, math.ceil(math.sqrt(i))+1):
            if i%k == 0:
                i_is_prime = False
                break
            else:
                pass
        if i_is_prime:
            break
        else:
            i_is_prime = True
            i += 1

print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
n = int(input())
def is_prime(n):
    for i in range(2,math.ceil(n**1/2)+1):
        if n % i == 0:
            return False
    return True    
i = n
while True:
    if is_prime(i): break
    i += 1
print(i)

Submission status: Accepted

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

while x>2:
    judge=True
    for i in range(2,x):
        if x%i==0:
            judge=False
            break
    if judge==True:
        num=x
        break
    x+=1
print(num)

Submission status: Accepted

Solution code:
import math

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

    return True

while prime(x) == False:
    x += 1
print(x)

Submission status: Accepted

Solution code:
import bisect
x = int(input())
n = 10**5
prime = [True]*(n+1)
prime[0] = False
prime[1] = False
P = []
for i in range(2,n+1):
  if not prime[i]:
    continue
  else:
    for j in range(2*i,n+1,i):
      prime[j] = False
for i in range(n+1):
  if prime[i]:
    P.append(i)
P.append((10**5)+3)
k = bisect.bisect_left(P,x)
print(P[k])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
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


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

    while is_prime(X):
        X += 1
    print(X)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X = INT()

if X == 2:
	print(2)
	exit()
if X == 3:
	print(3)
	exit()

for i in range(X, mod):
	flag = 0
	if i % 2 == 0:
		continue
	elif i % 3 == 0:
		continue
	else:
		for j in range(2, int(sqrt(i)) + 1):
			if i % j == 0:
				flag = 1
				break
		if flag == 0:
			print(i)
			exit()

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

inf = 10**20
if is_prime(X) == True:
	print(X)

else:
	for i in range(X+1,inf):
		if is_prime(i) == True:
			print(i)
			break

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
x=int(input())
while any(x%i<1 for i in range(2,x)):
  x+=1
print(x)

Submission status: Accepted

Solution code:
X = int(input())
while any(X%i == 0 for i in range(2,X)):
  X += 1
print(X)

Submission status: Accepted

Solution code:
import math

def primeCheck(n):
	if n == 2:
		return True
	else:
		mx = math.ceil(n ** 0.5)
		for i in range(2, mx + 1):
			if n % i == 0:
				return False
				break
			elif i == mx:
				return True

x = int(input())

for i in range(x, 10**6):
	if primeCheck(i):
		print(i)
		break

Submission status: Accepted

Solution code:
X = int(input())

hantei = True

for o in range(X,10**10):
	hantei = True
	for i in range(2,o):
		if(o % i == 0):
			hantei = False
	if(hantei == True):
		print(o)
		break

Submission status: Accepted

Solution code:
x = int(input())
num = 0

for i in range(x,x*2):
    for j in range(2,x//2):
        if i%j == 0:
            num += 1
            continue
    if num == 0:
        print(i)
        exit(0)
    num = 0

Submission status: Accepted

Solution code:
import sys
X = int(input())
def is_prime(X):
    for i in range(2,X):
        if X % i == 0:
            return False
    return True
if is_prime(X):
    print(X)
    sys.exit(0)
else:
    while True:
        if X%2 == 0:
            X+=1
        else:
            if is_prime(X):
                print(X)
                sys.exit(0)
            X+=2

Submission status: Accepted

Solution code:
import sys
X = int(input())
def is_prime(X):
    for i in range(2,X):
        if X % i == 0:
            return False
    return True
if is_prime(X):
    print(X)
    sys.exit(0)
else:
    while True:
        if X%2 == 0:
            X+=1
        else:
            if is_prime(X):
                print(X)
                sys.exit(0)
            X+=2

Submission status: Accepted

Solution code:
x = int(input())

ans = 0
while True:
    c = 2
    while True:
        
        if c > (x//2) :
            ans = x
            break
        if x % c == 0:
            break
        
        c += 1

    if ans != 0:
        break
    x += 1
print(x)

Submission status: Accepted

Solution code:
x = int(input())


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

    for k in range(2, int(n ** (1 / 2) + 1)):
        if n % k == 0:
            return False

    return True


def main():
    for i in range(10000):
        if is_prime(x + i):
            print(x + i)
            return


main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

def get_prime_list(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]]


X = int(input())
primes = get_prime_list(100100)
print(primes[bisect_left(primes, X)])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return {i for i in range(n + 1) if is_prime[i]}


prime_set = primes(10 ** 6)
n = I()
while True:
    if n in prime_set:
        break
    n += 1


print(n)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math

X = int(input())


while True:
    b = False
    for k in range(2, int(math.sqrt(X)) + 1):
        if X % k == 0:
            b = True
    if not b:
        break
    else:
        X += 1
print(X)

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 len(divisors)
  
ans = 0
while  True:
  ans = make_divisors(x)
  if ans == 2:
    break
  else:
#    continue
    x +=1

print(x)

Submission status: Accepted

Solution code:
x = int(input())


def prime_factorize(n):
    p = []
    while n % 2 == 0:
        if 2 not in p:
            p.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in p:
                p.append(f)
            n //= f
        else:
            f += 2
    if n != 1 and n not in p:
        p.append(n)
    return p


if x == 1:
    print(1)
else:
    while (1):
        a = prime_factorize(x)
        if len(a) == 1 and a[0] == x:
            print(x)
            exit()
        x += 1

Submission status: Accepted

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

def bool(X):
	for i in range(2,X):
		if X%i==0:
			flag=True
			return flag

	flag=False
	return flag

flag=True
while flag:
	flag=bool(X)
	if flag==False:
		break
	X+=1
print(X)

Submission status: Accepted

Solution code:
x=int(input())
if(x%2==0):
    a=x/2
else:
    a=x//2
y=2*a+1
import math
def is_prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
    return True
while(True):
    if(is_prime(y)):
        break
    y=y+2
if(x==2):
    y=2
print(str(int(y)))

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)

    return divisors
N = X -1
while(1):
    N +=1
    com = make_divisors(N)
    if len(com) == 2:
        ans = N
        break
print(ans)

Submission status: Accepted

Solution code:
import math

X = int(input())

def prime(x):
    if x >=3:
        if x % 2 == 0:
            return False
        else:    
            T = True
            i = 2
            while (T == True)&(1 < i <= math.ceil(math.sqrt(x))):
                if x % i == 0:
                    T = False
                i +=1
            return T
    else:
        return True

if X == 2:
    print(2)
elif X % 2 == 0:
    T = X + 1
    while (prime(T) == False):
        T +=2
    print(T)
else:
    T = X
    while (prime(T) == False):
        T +=2
    print(T)

Submission status: Accepted

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

def is_prime(x):
    if x <= 1: 
        return False
    for i in range(2,math.ceil(x**0.5)):
        if x%i==0: 
            return False
    return True
    
def main():
    x = int(input())
    for i in range(x, 100004):
        if is_prime(i):
            print(i)
            return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def is_prime(x):
    if x <= 1: 
        return False
    for i in range(2,math.ceil(x**0.5)):
        if x%i==0: 
            return False
    return True
def main():
    x = int(input())
    p = x
    while not is_prime(p):
        p += 1
    print(p)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def multiples(n):
    for i in range(3,100003):
        yield i*n
        if i*n > 100003:
            break

def sosuu(x):
    if x == 2 : return 2
    d = set()
    end = math.ceil(math.sqrt(x))
    d = d.union(multiples(2))
    for i in range(3,end,2):
        if i not in d:
            d = d.union(set(multiples(i)))
    
    i = x if x % 2 != 0 else x+1
    while True:
        if i not in d:
            return i
        i += 2

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
X = int(input())
for i in range(X, 10 ** 6):
    r = math.floor(X ** 0.5)
    for j in range(1, r + 1):
        if i % j == 0 and j != 1:
            break
        if j == r:
            print(i)
            exit()

Submission status: Accepted

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


x = int(input())

prime = [True] * (100004)
prime[2] = True

def e_prime(x):
	i = 2
	flag = False
	while True:
		if(i==x):flag=True
		if prime[i]:
			if(flag==True):
				return i
			else:
				for j in range(i**2,len(prime),i):
					prime[j]=False
		i+=1

print(e_prime(x))

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

for n in range(int(input()),10**5+100):
    if is_prime(n):
        print(n)
        break