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:
n = int(input())

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

print(n)

Submission status: Accepted

Solution code:
import math

num = int(input())

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

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

Submission status: Accepted

Solution code:
# ABC149 C - Next Prime
X = int(input())

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ABC149 C - Next Prime
X = int(input())

def isPrime(n):
    cnt = 0
    for i in range(1, n + 1):
        if n % i == 0:
            cnt += 1
    if cnt == 2:
        return True
    else:
        return False

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

Submission status: Accepted

Solution code:
def sosu(num):
    for i in range(2, num//2):
        if num % i == 0:
            return False
    return True


a = int(input())
i = 0
while True:
    if sosu(a + i):
        print(a + i)
        break
    i += 1

Submission status: Accepted

Solution code:
x = int(input())

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

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

Submission status: Accepted

Solution code:
import math

check = 1
X = int(input())

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

Submission status: Accepted

Solution code:
import math
X = int(input())
def f(X):
  if X <= 1:
    return False
  for i in range(2, int(math.sqrt(X))+1):
    if X%i==0:
      return False
  return True
while not f(X):
  X += 1
print(X)

Submission status: Accepted

Solution code:
x=int(input())
if x==2:
  print(2)
else:
  prime = False
  while prime == False:
    c=0
    for i in range(2,int(x**0.5)+1):
      if x%i != 0:
        c=c+1
    if c==int(x**0.5)-1:
      print(x)
      prime=True
    x=x+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
  
  # nの平方根まで計算する
  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,10**6):
  if isPrime(i):
    print(i)
    exit(0)

Submission status: Accepted

Solution code:
def prime(x):
    if x in [2,3,5,7,11]:
        return 1
    elif x % 2 ==0:
        return 0
    else:
        p=3
        while p*p <= x:
            if x % p ==0:
                return 0
            else:
                p += 2
        return 1


N=int(input())
for i in range(100):
    if prime(N+i):
        print(N+i)
        break

Submission status: Accepted

Solution code:
X = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())
mx = 100004
array = [1 for _ in range(mx)]
array[0] = array[1] = 0
for i in range(4, mx, 2):
    array[i] = 0
for i in range(3, mx, 2):
    if not array[i]:
        continue
    for j in range(i+i, mx, i):
        array[j] = 0
for i in range(n, mx):
    if array[i]:
        print(i)
        break

Submission status: Accepted

Solution code:
import math

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


x = int(input())

while True:
    if check_prime(x):
        print(x)
        exit()
    x += 1

Submission status: Accepted

Solution code:
x = int(input())
l = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313]

l = [ i for i in l if i < x]

m = [x % i for i in l]

while True:
    if not any(t == 0 for t in m):
        break
    m = [(i + 1) % l[n] for n, i in enumerate(m)]
    x += 1
print(x)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
x=int(input())

mod=10**7+9
for i in range(x,mod):
  if not any(i%j==0 for j in range(2,i+1-1)):
    ans=i
    break
    
print(ans)

Submission status: Accepted

Solution code:
def isPrime(n) : 
  
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
  
    # This is checked so that we can skip  
    # middle five numbers in below loop 
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True
x=int(input())
while True:
  if isPrime(x):
    print(x)
    break
  x+=1

Submission status: Accepted

Solution code:
#探索範囲増やすとどのくらい時間が伸びるのか

x=int(input())

def is_prime(p):
  cnt=0
  for i in range(2,p):
    if p%i==0:
      cnt+=1
  if cnt==0:
    return True
  #2からp-1までみて、cntが0ならpは素数
  else:
    return False
      
#print(*[(x,is_prime(x)) for x in range(1,10+1)])
num=x
while True:
  if is_prime(num):
    ans=num
    break
  num+=1
print(ans)

Submission status: Accepted

Solution code:
x=int(input())

def is_prime(p):
  cnt=0
  for i in range(1,int(p**0.5)+1):
    if p%i==0:
      cnt+=1
  if cnt==1:
    return True
  else:
    return False
      
#print(*[(x,is_prime(x)) for x in range(1,10+1)])
num=x
while True:
  if is_prime(num):
    ans=num
    break
  num+=1
print(ans)

Submission status: Accepted

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

X = int(input())
ret = 0
for i in range(X, 10**9):
    if judge(i):
        ret = i
        break
print(ret)

Submission status: Accepted

Solution code:
from sys import stdin
import math


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


x = int(stdin.readline().rstrip())
while not isPrime(x):
    x += 1
print(x)

Submission status: Accepted

Solution code:
x=int(input())
tempX=x
num=[]
ans=0
for i in range(x):
  if i!=0:
    if i !=1:
      num.append(i)
if x==2:
  ans=2
while ans==0:
  for i in num:
    if tempX%i == 0:
      tempX=tempX+1

      break
    if i==num[-1]:
      ans = tempX
print(ans)

Submission status: Accepted

Solution code:
import math
def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True
x = int(input())
while(not isPrime(x)):
    x += 1
print(x)

Submission status: Accepted

Solution code:
X = int(input())

def isPrime(n):
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    for p in range(3, int(n**0.5)+1, 2):
        if n % p == 0:
            return False
    return True

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X = int(input())

isPrime = [True] * 1000000
for p in range(2, 1000000):
    if not isPrime[p]:
        continue
    if p >= X:
        print(p)
        break
    for i in range(p + p, 1000000, p):
        isPrime[i] = False

Submission status: Accepted

Solution code:
def getdata_input():
    while True:
        yield input()
def callFunc2(it):
    N=int(next(it))
    prime=[x for x in range(2,2*N+1)]
    a=[-1]*(2*N+1)
    lp=0
    for x in prime:
        if lp >= N:
            break
        if a[x]!=-1:
            continue
        c=1
        i=x*c

        while i < 2*N+1:
            lp=x
            a[i]=x
            c+=1
            i=x*c
    return(str(lp))   
it=getdata_input()
print(callFunc2(it))

Submission status: Accepted

Solution code:
x = int(input())

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

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

Submission status: Accepted

Solution code:
X = int(input())

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

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

Submission status: Accepted

Solution code:
X=int(input())

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

Submission status: Accepted

Solution code:
def j_p(a):
    if a<=1:
        return False
    else:

        for i in range(2,a):
            if i**2>a:
                break
            else:
                if a%i==0:
                    return False
                else:
                    continue
        return True
x=int(input())
p=x
while j_p(p)==False:
    p+=1
print(p)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from fractions import gcd
from itertools import count
from functools import lru_cache
from collections import defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    x = ii()
    ps = []
    for i in count(2):
        is_prime = True
        for p in ps:
            if i % p == 0:
                is_prime = False
                break
            if i**0.5 < p:
                break 
        if is_prime:
            if x <= i:
                print(i)
                return
            else:
                ps.append(i)

main()

Submission status: Accepted

Solution code:
import math
 
x = int(input())
i = x
def prime(i):
    for j in range(2,math.ceil(math.sqrt(i))):
        if i%j == 0:
            return False
    return True

while True:
    if prime(i):
        print(i)
        break
    else:
        i += 1

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 divisors


while True:
    divisors = make_divisors(x)
    if len(divisors) == 2:
        print(x)
        exit(0)
    x += 1

Submission status: Accepted

Solution code:
X = int(input())

x = X
cnt = 0
prime_num_cnt = False

while True:
  for i in range(2,x):
    if x % i != 0:
      cnt += 1
  if cnt == (x-2):
    print(x)
    break
  cnt = 0
  x += 1

Submission status: Accepted

Solution code:
X = int(input())

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

Submission status: Accepted

Solution code:
a=int(input())

flag=True
while flag:
    for i in range(1,a):
        if(i==a-1):

            flag=False
        elif(a%i==0 and i!=1):
            a+=1
            break
print(a)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

X = int(input())

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

Submission status: Accepted

Solution code:
# C - Next Prime

def eratosthenes(n):
    numbers = [True] * (n + 1)
    primes = []
    for i in range(2, int(n ** 0.5 + 1)):
        if numbers[i]:
            for j in range(i*i, n + 1, i):
                numbers[j] = False
    for i in range(n+1):
        if numbers[i]:
            primes.append(i)
    return primes





primes = eratosthenes(1000000)
given = int(input())
for i in primes:
    if i >= given:
        print(i)
        break

Submission status: Accepted

Solution code:
x=int(input())
sosu=[False]*(10**5+4)
for i in range(2,10**5+4):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            break
    else:
        sosu[i]=True
for i in range(x,10**5+4):
    if sosu[i]:
        print(i)
        break

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:
x =int(input())
n = 2*10**5

is_prime = [True]*(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

for i in range(x-1,n):
    if is_prime[i]==True:
        print(i+1)
        break

Submission status: Accepted

Solution code:
import math
def isprime(n):
    if n==1:return(False)
    if n==2:return(True)
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:return(False)
    return(True)
n=int(input())
for i in range(n,10**6):
    if isprime(i):
        print(i)
        exit()

Submission status: Accepted

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

def using_sqrt(k):
    factor = 0
    
    # 2以外の偶数は素数ではないので無視する
    if k % 2 == 0 and k != 2:
        return False
    
    # 繰り返しの上限を対象の平方根にする
    for divisor in range(2, math.floor(math.sqrt(k))+1):
        if k % divisor == 0:
            factor += 1
            
    if factor == 0:
        return True
    else:
        return False
            

for i in range(x,110001):
    if using_sqrt(i):
        print(i)
        break

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

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