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:
from math import sqrt

x = int(input()) - 1
if x in (1, 2):
    print(x+1)
    exit()

while True:
    x += 1
    
    if x % 6 != 1 and x % 6 != 5:
        continue
    
    x_sqrt = int(sqrt(x))
    for a in range(2, x_sqrt+1):
        if x % a == 0:
            break
    else:
        print(x)
        break

Submission status: Accepted

Solution code:
from math import sqrt

x = int(input()) - 1
pnums = []
if x >= 4:
    for i in range(2, int(sqrt(x))+1):
        for j in pnums:
            if i % j == 0:
                break
        else:    
            pnums.append(i)

while True:
    x += 1
    x_sqrt = sqrt(x)
    if x_sqrt.is_integer():
        pnums.append(x_sqrt)
        continue
    
    for a in pnums:
        if x % a == 0:
            break
    else:
        print(x)
        break

Submission status: Accepted

Solution code:
import numpy as np
def make_prime(U):
    is_prime = np.zeros(U,np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5)+1
    for p in range(3,M,2):
        if is_prime[p]:
            is_prime[p*p::p+p] = 0
    return is_prime.nonzero()[0] #, is_prime

primes = make_prime(10 ** 5 + 10000)
n = int(input())
i = np.where(primes >= n)[0][0]
print(primes[i])

Submission status: Accepted

Solution code:
import math

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

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

x = int(input())

print(next_prime(x))

Submission status: Accepted

Solution code:
import math as m

x = int(input()) - 1
flg = 1
while flg == 1:
    flg = 0
    x += 1
    a = int(m.sqrt(x)//1 + 1)
    for i in range(2, a):
        if x % i == 0:
            flg = 1
            break

print(x)

Submission status: Accepted

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

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

def check(X):
    for i in range(X,10**100):
        if is_prime(i):
            return i
    
print(check(X))

Submission status: Accepted

Solution code:
x = int(input())
if x == 2:
    print('2')
    exit()
ans = 0
while ans == 0:
    for i in range(2, x):
        if x % i == 0:
            break
        if i == x - 1 and x % i != 0:
            print(x)
            exit()
    x += 1

Submission status: Accepted

Solution code:
import math
X=int(input())
flag=0
ans=0
for i in range(100000):
      for j in range(2,round(math.sqrt(X))):
          if (X+i)%j==0:
              flag=1
              break
      if flag==0:
          ans=i
          break
      else:
          flag=0
print(ans+X)

Submission status: Accepted

Solution code:
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True

    limit = n ** 0.5
    for i in range(2 , n):
        if n % i == 0:
            return False
        if i >= limit: 
            return True

x = int(input())

n = x

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

print(n)

Submission status: Accepted

Solution code:
import math
import bisect

X = int(input())

N = 100100
primes = [i for i in range(X + 100)]
primes[1] = 0

for prime in primes:
    if prime > math.sqrt(N):
        break
    if prime == 0:
        continue
    for non_prime in range(2 * prime, X + 100, prime):
        primes[non_prime] = 0
    
lpm = [prime for prime in primes if prime != 0]
i = bisect.bisect_left(lpm, X)
print(lpm[i])

Submission status: Accepted

Solution code:
x = int(input())

def Eratosthenes(x):
    n = [i for i in range(2,x+1)]
    prime_list = []

    while True:
        if n[0] >= x**0.5:
            prime_list.extend(n)
            break
        tmp = n.pop(0)
        prime_list.append(tmp)
        n = [i for i in n if i % tmp != 0]

    return prime_list

primes = Eratosthenes(10**5+3)

ans = x
while True:
    if x in primes:
        print(x)
        break
    else:
        x += 1

Submission status: Accepted

Solution code:
x = int(input())

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

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

Submission status: Accepted

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

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

    MAX_PRIME = int(1e5) + 100
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    for p in primes:
        if p >= x:
            print(p)
            break
    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(x)

Submission status: Accepted

Solution code:
from math import sqrt

N = 10**6

is_prime = [True] * (N + 1)
is_prime[0] = False
is_prime[1] = False

n = int(sqrt(N) + 1)
for i in range(4, N+1, 2):
   is_prime[i] = False

for i in range(3, n+1, 2):
   if is_prime[i]:
      for j in range(i+i, N+1, i):
         is_prime[j] = False

x = int(input())
for i in range(x, N+1):
   if is_prime[i]:
      print(i)
      break

Submission status: Accepted

Solution code:
X=int(input())
check=0
for i in range(X,2*X):
    check=0
    for j in range(2,int(i**(1/2))):
        if i%j!=0:
            pass
        else:
            check=1
            break
    if check==0:
        print(i)
        break

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

def main():
    X = int(input())
    for i in range(pow(10,5)):
        num = X + i
        if(is_prime(num)):
            print(num)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
x = int(input())

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

Submission status: Accepted

Solution code:
x = int(input())
def is_prime(x):
    if x<2:
        return False
    for n in range(2,x):
        if x% n == 0:
            return False
    return True
while not is_prime(x):
    x += 1
print(x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Mar  4 19:06:03 2020

@author: Kanaru Sato
"""
import math

X = int(input())

target = X
flag = 0

if X == 2 or X == 3:
    flag = 1

while flag == 0:
    rootX = int(math.sqrt(X))
    for i in range(2, rootX+1):
        if X%i == 0:
            if X%2 == 0:
                X += 1
                break
            else:
                X += 2
                break
        elif i == rootX:
            flag = 1
            break
        else:
            continue

print(X)

Submission status: Accepted

Solution code:
x=int(input())
if x==2:
  print(2)
  exit()

for i in range(x,x*100):
  for j in range(2,int(x**0.5)+2):
    if i%j==0:
      break
  else:
    print(i)
    exit()

Submission status: Accepted

Solution code:
x=int(input())

def is_prime(x):
    if x==2:
        return 1
    if x<2 or x%2==0:
        return 0
    i=3
    while i<=x**0.5:
        if x%i==0:
            return 0
        i+=2
    return 1
for i in range(x,x+10**5):
    if is_prime(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
import math

def is_sosuu(X):
  # 2以外の偶数は素数ではないので無視する
  if X % 2 == 0 and N != 2:
    return False
  
  # 繰り返しの上限を対象の平方根にする
  limit = int(math.sqrt(X)) + 1
  # ２の倍数を省く
  numbers = [i for i in range(3, limit) if i % 2 == 1]
  for i in numbers:
    if X % i == 0:
      return False

  return True

N = int(input())
while True:
  if is_sosuu(N):
    print(N)
    break
  N+=1

Submission status: Accepted

Solution code:
x  = int(input())
def p(x):
    i = 2
    if x <= 1:
        return False
    while i*i <= x:
        if x%i == 0:
            return False
        i += 1
    return True
while True:
    if p(x) == True:
        print(x)
        break
    x += 1

Submission status: Accepted

Solution code:
import sys
x=int(input())
for i in range(x,2*x+1):
  for j in range(2,int(i**0.5)+1):
    if i%j==0:
      break
  else:
    print(i)
    sys.exit()

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

# returnの位置
# 割り切れない時はTrueを返して、割り切れるときはFalseを返す

while not prime(x):
    x += 1
print(x)
# prime(n)は素数判定機となっているので、while文を素数じゃないときまで回す

Submission status: Accepted

Solution code:
x = int(input())

while True:
    prime = []
    for i in range(1, x, 2):
        if x % i == 0:
            prime.append(i)
    if len(prime) == 1:
        print(x)
        break
    else:
        x += 1

Submission status: Accepted

Solution code:
def check(n):
    for i in range(2,n):
        if ((n%i)==0):
            return 0
    return n

x = int(input())
prime = 0
while prime == 0:
    prime = check(x)
    x += 1
print(prime)

Submission status: Accepted

Solution code:
x=int(input())
while 1:
  if all(x%i for i in range(2,int(x**.5)+1)):
    print(x); break
  x+=1

Submission status: Accepted

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


class Prime:
    # https://qiita.com/daikw/items/f48d6ac374255763463d
    seed_primes = [
        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
    ]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

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

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed + 1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


judge = Prime().is_prime
for x in range(X, X + 10000):
    if judge(x):
        print(x)
        exit()

Submission status: Accepted

Solution code:
x=int(input())
ans=100003  
for i in range(x,10**5+1):
    if all(i%j!=0 for j in range(2,x)):
        ans=i
        break
print(ans)

Submission status: Accepted

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

a = 10**6+1
b = [True]*(a)
b[0] = False
b[1] = False

for i in range(4, a, 2):
  b[i] = False

p = int(math.sqrt(a))
for i in range(3, p+1, 2):
  if b[i]:
    for j in range(i+i, a, i):
      b[j] = False

ans = 0
for i in range(x, a):
  if b[i]:
    print(i)
    break

Submission status: Accepted

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

for i in range(x,10**6):
    if x == 2:
        print(2)
        exit()
    flag = judge(i)
    if flag == True:
        print(i)
        exit()

Submission status: Accepted

Solution code:
x = int(input())

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

Submission status: Accepted

Solution code:

import math
x = int(input())

def Is_prime(a):
	flag = 0
	for k in range(2,int(math.sqrt(a))+1):
		if a%k == 0:
			flag = 1
	if flag == 0:
		return True
	else:
		return False

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

# below is good site about prime number
#https://www.takapy.work/entry/2018/06/26/220608

Submission status: Accepted

Solution code:
X=int(input())
ans=0
for i in range(X,2*X+1):
    for j in range(2,i):
        if i%j!=0:
            ans+=1
    if ans==i-2:
        print(i)
        exit()
    else:
        ans=0

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 = x + 1
            break
    else:
        print(x)
        exit()

Submission status: Accepted

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

def Is_prime(a):
	flag = 0
	for k in range(2,int(math.sqrt(a))+1):
		if a%k == 0:
			flag = 1
	if flag == 0:
		return True
	else:
		return False

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

Submission status: Accepted

Solution code:
import math
n = int(input())
prime = []
for i in range(2,math.floor(n**0.5)+1):
    for k in range(len(prime)):
        if i % prime[k] == 0: 
           break
    else:
        prime.append(i)
for i in range(10000):
    for k in range(len(prime)):
        if (n+i) % prime[k] == 0:
            break
    else:
        print(n+i)
        exit()