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())
testX=int(X**(1/2))+2
primeset=set()
for i in range(2,testX):
    num=0
    for p in primeset:
        if i%p != 0:
            pass
        else:
            num=1
            break
    if num==0:
        primeset.add(i)
num=0
if X in primeset:
    print(X)
    num=1
while num == 0:
    num=1
    for p in primeset:
        if X%p != 0:
            pass
        else:
            X+=1
            num=0
            break
    if num == 1:
        print(X)

Submission status: Accepted

Solution code:
X = int(input())
def is_prime(x):
    flag = True
    for i in range(2,int(x**(0.5))+1):
        if x % i == 0:
            flag = False
    return flag
for i in range(X,2*X+1):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
X = int(input())
isPrime = False
while not isPrime:
  isPrime = True
  for i in range(2, X):
    if X % i == 0:
      isPrime = False
  if isPrime == True:
    break
  X += 1
print(X)

Submission status: Accepted

Solution code:
n = int(input())

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

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

Submission status: Accepted

Solution code:
'''input
3 5
1 2 1
2 3 0
'''
# connected components
from sys import stdin, setrecursionlimit
from bisect import bisect_left

# main starts
x = int(stdin.readline().strip())
mx = 10 ** 6 + 1
seive  = [0] * mx
prime = []
for i in range(2, mx):
    if seive[i] == 0:
        prime.append(i)
        for j in range(i* i, mx, i):
            seive[j] = 1
print(prime[bisect_left(prime, x)])

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
prime_sieve=[1 for i in range(200000)]

prime_sieve[0]=0
prime_sieve[1]=0

X=int(input())
for i in range(2,200000):
  if prime_sieve[i]==1:
    if i>=X:
      print(i)
      break
    else:
      for j in range(2,200000//i):
        prime_sieve[i*j]=0

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
nn=int(input())
n=10**5+100
ar=[0]*(n)
ar[1]=0
ans=0
pre=1
for i in range(2,int((n**0.5))+1):
    if ar[i]==0:

        for j in range(2*i,n,i):
            ar[j]=1
ans=1
if ar[nn]==0:
    print(nn)
else:
        
    for i in range(nn,n):
        if ar[i]==0:
            print(i)
            break

Submission status: Accepted

Solution code:
nn=int(input())
n=10**5+100
ar=[0]*(n)
ar[1]=0
ans=0
pre=1
for i in range(2,n):
    if ar[i]==0:

        for j in range(2*i,n,i):
            ar[j]=1
ans=1
if ar[nn]==0:
    print(nn)
else:
        
    for i in range(nn,n):
        if ar[i]==0:
            print(i)
            break

Submission status: Accepted

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

def judge_prime(number):
  n = math.floor(number**0.5)
  ar=list(range(n))+[n]
  ar.pop(0)
  ar.pop(0)
  for i in ar:
    if number%i==0:
      return 0
  return number

t = 0
while t == 0:
  if judge_prime(number) == number:
    t+=1
  else:
    number+=1
print(number)

Submission status: Accepted

Solution code:
X = int(input())
is_prime = [True] * (X + 1)
is_prime[1] = False
for i in range(2, X + 1):
    if not is_prime[i]:
        continue
    now = i
    while now + i <= X:
        now += i
        is_prime[now] = False
candidate = X
while True:
    candidate_prime = True
    for i in range(2, X + 1):
        if i ** 2 > X:
            break
        if not is_prime[i]:
            continue
        if candidate % i == 0:
            candidate_prime = False

    if candidate_prime:
        print(candidate)
        exit()
    else:
        candidate += 1

Submission status: Accepted

Solution code:

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n = ii()
    ans = list(range(100005))
    flag = [0 for i in range(100005)]
    flag[0] = 1
    flag[1] = 1
    for ind in range(100005):
        if flag[ind] == 1:
            continue
        tmp = ind
        
        while tmp+ind < 100005:
            tmp+=ind
            flag[tmp] = 1

        
    


    for i in range(100005):
        if flag[n+i] == 0:
            print(n+i)
            exit()

    



    


    
main()

Submission status: Accepted

Solution code:
import sys

def main():
    # sys.stdin = open('input149c.txt')

    x = int(input())

    r = False
    while not r:
        r = True
        for i in range(2,x):
            if x % i == 0:
                r = False
                break

        if r == False:
            x += 1
        
    print(x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
X = int(input())

max_n = 100003
primes = [True] * (max_n+1)

for i in range(2,max_n+1):
  if primes[i] == True:
    if i >= X:
      print(i)
      break
    for j in range(i+i, max_n+1, i):
      primes[j] = False

Submission status: Accepted

Solution code:
import math

X = int(input())

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

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

print(str(X))

Submission status: Accepted

Solution code:
x=int(input())
xr=100010


s=[True for _ in range(xr)]

for i in range(2, xr):
    if s[i]:
        se=i*2
        while se < xr:
            s[se]=False
            se+=i


while True:
    if s[x] == True:
        print(x)
        exit()
    else:
        x+=1

Submission status: Accepted

Solution code:
import math
X = int(input())
number = 2
while (1):
    flag = 1
    for i in range(2, int(math.sqrt(number))+1):
        # print(i)
        if number % i == 0:
            flag = 0
            break
    if flag == 1:
        if number >= X:
            print(number)
            break
    number += 1

Submission status: Accepted

Solution code:
x = int(input())
y = x + 100
is_prime = [False] * 2 + [True for _ in range(2, y+1)]
prime = []
for i in range(2, y+1):
	for j in range(i*2, y+1, i):
		is_prime[j] = False
for i in range(y+1):
	if is_prime[i]:
		prime.append(i)
for i in range(len(prime)):
  if prime[i] >= x:
    print(prime[i])
    break
  else:
    continue

Submission status: Accepted

Solution code:
def is_prime(n):
    if n == 1:
        return True
    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:
    ans = x
    break
  x += 1

print(ans)

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())
ans = x
while is_prime(ans) is False:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math

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

x=int(input())
while True:
  if check(x):
    print(x)
    break
  x+=1

Submission status: Accepted

Solution code:
x = int(input())

def sosu(x):
    sw = 1
    for i in range(x):
        amr = x % (i + 1)
    
        if 1 < (i + 1) < x: #１より大きい数で割ったとき
            if amr == 0: #余り０
                sw = 0
    return sw

while sosu(x) ==0:
    x += 1

print(x)

Submission status: Accepted

Solution code:
n = int(input())
ans = False
while not ans:
	ans = True
	for i in range(2,int(n ** (1/2))+1):
		if n % i ==  0:
			ans = False
			break
	n = n + 1
print(n-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


n = int(input())
for i in range(n, 10**10):
    if is_prime(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
X = int(input())
import math
def isprime(x):
    if x < 2:
        return False
    elif x == 2:
        return True
    elif x%2 == 0:
        return False
    for i in range(3,math.floor(math.sqrt(x)+1),2):
        if x%i == 0:
            return False
    return True

for x in range(X,100004):
    if isprime(x):
        print(x)
        exit()

Submission status: Accepted

Solution code:
x = int(input())
a = False
while a == False:
  b = list(range(1,x) ) 
  c = [x/c for c in b]
  d = [d.is_integer() for d in c[1:-1]]
  if not any(d):
    a = True
    break    
  else:
    x = x + 1
print(x)

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(100000):
    if isPrime(x+i):
        break
    else:
        continue
print(x+i)

Submission status: Accepted

Solution code:
import math

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


X = int(input().strip())
ans = 0
for i in range(X, (10 ** 6 + 1), 1):
    if is_prime(i):
        ans = i
        break
print(ans)

Submission status: Accepted

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

while True:
  m = int(math.sqrt(x))
  
  prime = True
  for i in range(2, m+1):
    if x%i==0:
      prime = False
      break
  if prime:
    print(x)
    break
  x += 1

Submission status: Accepted

Solution code:
X = int(input())


def primes():
    """
    素数のジェネレータ
    """
    d = {}
    q = 2
    while True:
        if q not in d:
            yield q
            d[q * q] = [q]
        else:
            for p in d[q]:
                d.setdefault(p + q, []).append(p)
            del d[q]
        q += 1


for p in primes():
    if p >= X:
        print(p)
        exit(0)

Submission status: Accepted

Solution code:
X = int(input())
prime = 0
while not prime:
	i = 2
	while i <= int(X/2):
		if X % i == 0:
			X += 1
			break
		i += 1
	else:
		prime = 1
print(X)

Submission status: Accepted

Solution code:

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)
            return ass
    if ass[0] == 1:
        del ass[0]
    return ass



x = int(input())
print(segment_sieve(x, 100004)[0])

Submission status: Accepted

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

def solve():
  x = int(input())
  for i in range(x,10**6+15):
    if isprime(i):
      print(i)
      exit()
      
solve()

Submission status: Accepted

Solution code:
from math import ceil
x=int(input())
i=0
if x<=2:
  print(2)
elif x==3:
  print(3)
elif x==4:
  print(5)
else:
  while 1:
    ok=True
    n=ceil((x+i)**0.5)
    for j in range(2,n):
      if (x+i)%j==0:
        ok=False
        break
    if ok:
      print(x+i)
      exit()
    i+=1

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Next Prime
import numpy as np

# input
X = int(input())

# solve
prime = 0
numbers = np.array(list(range(2, 10**5 + 4)))

while prime < X:
    prime = numbers[0]
    numbers = numbers[numbers % prime != 0]

# output
print(prime)

Submission status: Accepted

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

x = int(input())
# print(x)

def is_prime(num):
    if num > 1:
        for i in range(2, num):
            if (num % i) == 0:
                return False
        return True
    else:
        # 1 is not prime
        return False

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  x = int(input())
  sosu = []
  tgt = 2
  is_sosu = True
  while(1):
    for i in sosu:
      if tgt % i == 0:
        is_sosu = False
        break
    if is_sosu:
      sosu.append(tgt)
    if tgt >= x and is_sosu:
      print(tgt)
      break
    else:
      tgt += 1
      is_sosu = True

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
x = int(input())

primes = [True]*(2*x)

for i in range(2, x):
    if primes[i]:
        for j in range(i, 2*x, i):
            primes[j] = False
for i in range(x, 2*x):
    if primes[i]:
        print(i)
        exit()

Submission status: Accepted

Solution code:
import math

X = int(input())

serach_number = 100003

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

    for i in range(10**5):
        if prime_list[i] < X:
            continue
        elif prime_list[i] >= X:
            print(prime_list[i])
            break

sieve_of_eratosthenes(serach_number)

Submission status: Accepted

Solution code:
#abc149c

def is_prime(n):
 if n < 2: 
  return False;
 if n % 2 == 0:             
  return n == 2
 k = 3
 while k*k <= n:
   if n % k == 0:
    return False
   k += 2
 return True

x=int(raw_input())
while not is_prime(x):
 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**0.5+1)):
        if n % k == 0:
            return False

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

Submission status: Accepted

Solution code:
x = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

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


x = int(input())

for i in range(x, 10 ** 6):
    if isPrime(i):
        print(i)
        exit()