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())
import math
for i in range(x, 10**5+100000):
  flag=True
  e = math.floor(math.sqrt(x))
  for j in range(2, e+1):
    if i%j == 0:
      flag=False
      break
  if flag==True:
    print(i)
    exit()

Submission status: Accepted

Solution code:
import sys
import math

A = raw_input()
A = int(A)

primes = []

for i in xrange(100004):
    if i <= 1:
        continue
    if not primes:
        primes.append(i)
        continue
    for j in primes:
        #print i, j, primes
        if i % j == 0:
            break
        if math.sqrt(i) < j:
            primes.append(i)
            break
    else:
        primes.append(i)
for x in primes:
    if x < A:
        continue
    print x
    break

Submission status: Accepted

Solution code:
import sys
import math
X = int(sys.stdin.readline())
if X ==2:
    print(2)
else:
    while True:
        for i in range(2, int(math.sqrt(X)+2)):
            if X%i==0:
                break
        else:
            print(X)
            break
        X+=1

Submission status: Accepted

Solution code:
import math

target = int(input())
while True:
  eval_val = int(math.sqrt(target))
  not_sosuu = False
  for i in range(2,eval_val):
    if target % i == 0:
      not_sosuu = True
      break

  if not_sosuu == False:
    print(str(target))
    break
  else:
    target += 1

Submission status: Accepted

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

x = int(input())
k = x
while(True):
    if is_prime(k):
        print(k)
        break
    else:
        k += 1

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


x = int(input())

MAX_PRIME = 100003
prime = np.array(range(MAX_PRIME+1))

prime[0:2] = 0
for i, v in enumerate(prime):
    if v == 0:
        continue
    prime[i*2::i] = 0

rst = MAX_PRIME
for i in range(x, MAX_PRIME+1):
    if prime[i] != 0:
        rst = i
        break

print(rst)

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:
    d = is_prime(x)
    if d == False:
        x += 1
    else:
        print(x)
        break

Submission status: Accepted

Solution code:
import math

N = int(input())

def sosuu(num):
  if num == 2:
    return (True)
  else:
    numsq = int(math.sqrt(num))
    judge = True
    for i in range(numsq):
      if (num % (i + 2) == 0):
        judge = False
        break
    return (judge)

while True:
  if (sosuu(N) == False):
    N+=1
  else:
    break;

print(N)

Submission status: Accepted

Solution code:
import math

def prime(x):
    limit = math.floor(math.sqrt(x))+1
    for divisor in range(2, limit):
        if x % divisor == 0:
            return False
    return True

x = int(input())
inf = 10**6

for i in range(x, inf):
    if prime(i):
        print(i)
        exit(0)

Submission status: Accepted

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

def primes(n):
    a = [True] * (n + 1)
    a[0] = False
    a[1] = False
    for i in range(2, int(math.sqrt(n))+1):
        for j in range(i * 2, n + 1, i):
            a[j] = False
    return [i for i in range(n + 1) if a[i]==True]

a = primes(x*5)

b = [a[i] for i in range(len(a)) if a[i]>=x]
print(min(b))

Submission status: Accepted

Solution code:
X=int(input())
n=10**6+1
primes=set(range(2,n+1))
for i in range(2,int(n**0.5+1)):
  primes.difference_update(range(i*2,n+1,i))
primes=list(primes)
for i in range(X,n):
  if i in primes:
    print(i)
    break

Submission status: Accepted

Solution code:
from bisect import bisect_left
INFTY = 10**5+10
P = [1 for _ in range(INFTY)]
P[0]=0
P[1]=0
for i in range(2,int(INFTY**0.5)+1):
    for j in range(i*i,INFTY,i):
        P[j] = 0
Q = []
for i in range(INFTY):
    if P[i]==1:
        Q.append(i)
X = int(input())
ind = bisect_left(Q,X)
print(Q[ind])

Submission status: Accepted

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

Submission status: Accepted

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

def qprime(n):
    if n<2:return False
    elif n==2:return True
    elif n%2==0:return False
    for i in range(3,math.floor(math.sqrt(n))+1,2):
                   if n % i == 0:return False
    return True


for i in range(X,10000000):
    if qprime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
def is_prime(num):
  i = 5
  while (i * i <= num):
      if num % i == 0 or num % (i+2) ==0:
          return False
      i+=6
  return True if num > 1 and num <=3 else False if num % 2 == 0 or num % 3 == 0 or num <=1 else True

k = int(input())
if is_prime(k):
  print(k)
else:
  while(not is_prime(k)):
    k +=1
  print(k)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    prime=[0,1]*500000
    prime[2]=1
    for x in range(3,500000):
        if prime[x]:
            for y in range(x**2,1000000,x):
                prime[y]=0
    x=II()
    for y in range(x,1000000):
        if prime[y]:
            print(y)
            break


main()

Submission status: Accepted

Solution code:
import numpy as np

number = int(input())

if number == 2:
    print(number)
else:
    first = 0
    for i in range(2, number):
        if number%i == 0:
            first = 1
            break
    if first == 0:
        print(number)
    else:
        for i in range(number + 1, 1000000000000):
            flag = 0
            for j in range(2, i):
                if i % j == 0:
                    flag = 1
                    break
            if flag == 0:
                print(i)
                break

Submission status: Accepted

Solution code:
import math

def Is(x):
  flag = False
  i = 2
  while i < math.sqrt(x):
    if x % i==0:
      flag = True
      break
    i += 1
  return flag

a = int(input())
ans = 0
flag2 = True
i = 0
while flag2:
  flag2 = Is( a + i )
  ans = a + i
  i += 1

print(ans)

Submission status: Accepted

Solution code:
import math 
def isPrime(n):
    if n == 1:
        return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
def nextPrime(N):
    if N <= 1:
        return 2
    prime = N
    found = False
    while(not found): 
        prime = prime + 1
        if(isPrime(prime) == True): 
            found = True
    return prime 
A = int(input())
N = A-1
print(nextPrime(N))

Submission status: Accepted

Solution code:
import bisect

def prime_sieve(end):
    assert end > 1
    is_prime = [True for i in range(end)]
    is_prime[0], is_prime[1] = False, False
    primes = list()
    for i in range(2,end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes #リスト型

x = int(input())
a = prime_sieve(150000)
ans = a[bisect.bisect_left(a,x)]
print(ans)

Submission status: Accepted

Solution code:
x=int(input())
def isprime(k):
  for i in range(k):
    if (i+2)*(i+2)>k:
      return True
    if k%(i+2)==0:
      return False

for k in range(x,100004):
  if isprime(k):
    print(k)
    break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x = int(input())
prime = [True for i in range(1000000)]
prime[0] = prime[1] = False
for i in range(200000):
    if prime[i]:
        for j in range(i+i, 200000, i):
            prime[j] = False
for i in range(x, 200000):
    if prime[i]:
        print(i)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X = int(input())
for num in range(X, 10000000000):
    if num > 1:
       for i in range(2, num):
           if (num % i) == 0:
               break
       else:
           print(num)
           break

Submission status: Accepted

Solution code:
import math

n=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


for i in range(n, 10**6):
  if is_prime(i):
    print(i)
    break

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
X = int(input())

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

def nextPrime(N): 
  
    # Base case  
    if (N <= 1): 
        return 2
  
    prime = N 
    found = False
  
    # Loop continuously until isPrime returns  
    # True for a number greater than n  
    while(not found): 
        prime = prime + 1
  
        if(isPrime(prime) == True): 
            found = True
  
    return prime 

if (isPrime(X)) : 
    print(X) 
else : 
    X = nextPrime(X)
    print(X)

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())
ifPrime = False

while ifPrime is False:
    ifPrime = True
    d = 2
    while ifPrime is True and d <= X**0.5:
        if X % d == 0:
            ifPrime = False
        d += 1
    X += 1

print(str(X - 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
box = [i for i in range(N,100004)]
box = [i for i in box if not i % 2==0]
box = [i for i in box if not i % 3==0]
box = [i for i in box if not i % 5==0]
box = [i for i in box if not i % 7==0]
primes = [2]
for i in range(3, N, 2):
    all(i % p != 0 for p in primes) and primes.append(i)
for i in box:
    if N ==2:
        print(2)
        break
    elif all(i % p != 0 for p in primes):
        print(i)
        break

Submission status: Accepted

Solution code:
import math
X=int(input())
if X==2:
  print(2)
  exit()
i=X
while i>0:
  flag=True
  for j in range(2,int(math.sqrt(i))+2):
    if i%j==0:
      flag=False
      break
  if flag==True:
    print(i)
    exit()
  i+=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


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

    while True:
        if is_prime(X):
            print(X)
            break

        X += 1


main()

Submission status: Accepted

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

X = int(input())
n = 2*X

candidate = list(range(2, n+1)) #候補
prime = []
limit = n**0.5 + 1 

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

for number in prime:
    if number >= X:
        print(number)
        exit()

Submission status: Accepted

Solution code:
import sys


x = int(input())

a = 10 ** 5

ans = x
if ans == 1:
    print(1)
    sys.exit()

for i in range(a):
    flag = True
    for j in range(2,int(ans**0.5)+1):
        if ans % j == 0:
            flag = False
    
    if flag:
        print(ans)
        sys.exit()
    else:
        ans = ans + 1

Submission status: Accepted

Solution code:
import math
def isprime(limit):
    if limit == 2:
        return 2
    for k in range(limit, limit + 100000):
        if k % 2 == 0:
            continue
        for divisor in range(2, math.floor(math.sqrt(k)) + 2):
            if k % divisor == 0:
                break
            if divisor == int(math.floor(math.sqrt(k)) + 1):
                return k
num = int(input())
print(isprime(num))

Submission status: Accepted

Solution code:
X = int(input())

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

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

print(X)

Submission status: Accepted

Solution code:
def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= x**(1/2):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

x = int(input())
for i in range(x,10**6+1):
    if is_prime(i):
        print(i)
        exit()
    else:
        pass

Submission status: Accepted

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

number = int(input())

def traial_division(target):
    dest = int(math.sqrt(target))
    for i in range(2,dest):
        if target % i == 0:
            return False
    #targetは素数
    return True

while True:
    if traial_division(number) == True:
        print(number)
        break
    else:
        number = number + 1

Submission status: Accepted

Solution code:
import math

X = int(input())

def isPrime(X):
  if X == 2:
    return True
  if X % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(X)) + 1
  for p in range(3, m, 2):
      if X % p == 0:
        return False
  return True

for i in range(1, 10**5):
    if isPrime(X) == True:
        print(X)
        exit()
    else:
        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


a = isPrime(X)

while a is False:
    X += 1
    a = isPrime(X)
else:
    print(X)

Submission status: Accepted

Solution code:
import math

def judgePrimeNumber(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 judgePrimeNumber(X) == False:
    if X % 2 == 0:
        X += 1
    else:
        X += 2

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

    # 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, x+200):
    if isPrime(i):
        print(i)
        break
    else:
        continue

Submission status: Accepted

Solution code:
import math

def trial_division(target):
    dest = int(math.sqrt(target))

    for i in range(2, dest):
        if target % i == 0:
            return False
    return True


def main():
    x = int(input())
    for i in range(x, (10**6)):
        if trial_division(i):
            print(i)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def is_prime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    from math import sqrt
    sqrtnum = sqrt(num)
    i = 3
    while (i <= sqrtnum):
        if num % i == 0:
            return False
        i += 2
    return True

X = int(input().rstrip())

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

Submission status: Accepted

Solution code:
# coding: utf-8
 
def is_prime2(q,k=100):
  q = abs(q)
  if q == 2: return True
  if q < 2 or q&1 == 0: return False
  for i in range(3,k):
    x,y = q,i
    while y:
      x, y =  y, x % y
    if x != 1: continue
    if pow(i, q-1, q) != 1:
      return False
  return True
 
X = int(input())
 
for i in range(X,10**5+4):
  if is_prime2(i):
    print(i)
    exit()

Submission status: Accepted

Solution code:
def isPrime(n):
    for i in range(2,N):
        if N%i == 0:
            return False
    return True
    
    
def find_next_prime(n):
    return find_prime_range(n, 2*n)

def find_prime_range(a, b):
    for p in range(a, b):
        for j in range(2, p):
            if p % j == 0:
                break
        else:
            return p
    return None

N = int(input())
if(isPrime(N)):
    print(str(N))
else:
    print(str(find_next_prime(N+1)))

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

while not is_prime(x):
  x+=1
print(x)

Submission status: Accepted

Solution code:
import math

n = int(input())

for i in range(0,1000) :

  v = n + i 
  
  l = int(math.sqrt(v)) 
  
  flg = False
  for i in range(2,l):
    
    if v % i == 0 :
      
      flg = True
      break
      
  if flg == False :
    
    print(v)
    exit()

Submission status: Accepted

Solution code:
X = int(input())

import math
import copy
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

def binary_search_exist(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        center = int((left + right) / 2)
        if target == nums[center]:
            return True
        elif target < nums[center]:
            right = center
        else:
            left = center + 1
    return False

def binary_search(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        center = int((left + right) / 2)
        if target == nums[center]:
            return center
        elif target < nums[center]:
            right = center
        else:
            left = center + 1
    return right

prime_list = sieve_of_eratosthenes(X + 1000)
if binary_search_exist(prime_list, X):
    print(X)
else:
    prime_list.append(X)
    prime_list.sort()
    r = binary_search(prime_list, X)
    print(prime_list[r + 1])

Submission status: Accepted

Solution code:
n = int(input())
def isPrime(n):
    for ele in range(2,int(n**0.5) +1):
        if n % ele == 0:
            return False
    return True
def main(n):
    if not isPrime(n):
        while True:
            n = n + 1
            if isPrime(n):
                return n
    else:
        return n

print(main(n))

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
for i in range(x,100004):
    if is_prime(i):
        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
  
n = int(input())
while True:
  if is_prime(n):
    print(n)
    exit()
  n += 1

Submission status: Accepted

Solution code:
import math
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
ans = n = int(input())
while not isPrime(ans):
    ans += 1
print(ans)

Submission status: Accepted

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

x = int(input())

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

print(x)

Submission status: Accepted

Solution code:
import math
A = int(input())
i = 0
S = 0
B = int(math.sqrt(A))
while i == 0:
    S = 0
    B = int(math.sqrt(A))
    for n in range(2,B + 1):
        if A % n == 0:
            A += 1
            S = 1
            break
    if S == 0:
        print(A)
        exit()

Submission status: Accepted

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

while flag==1:
  check=1
  for i in range(2,x):
    if x%i==0:
      check*=0
      break
    else:
      check*=1
  if check==1:
    flag*=0
  x+=1
print(x-1)

Submission status: Accepted

Solution code:
X = int(input())
def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P

P = primes(X)
y = X
while True:
    for p in P:
        if y % p == 0:
            break
    else:
        break
    y += 1
    continue
print(y)

Submission status: Accepted

Solution code:
X = int(input())

def sieve(n):
    prime = []

    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    
    for i in range(2, n + 1):
        if is_prime[i]:
            prime.append(i)
            
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
                
    return prime

for v in sieve(100007):
    if v >= X:
        print(v)
        break