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

n_2 = int(n**(1/2))

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

Submission status: Accepted

Solution code:
n = int(input().strip())

def next_higher(n):
    while True:
        s = str(n)
        if not any([n % i == 0 for i in range(2, int(n**0.5))]):
            return n
        n = n + 1

print(next_higher(n))

Submission status: Accepted

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

def prime_num(x):
    ret = x
    flag = False
    while True:
        for p in range(2, int(math.sqrt(ret)+1)):
            if ret % p == 0:
                flag = True
                break
        if flag == True:
            flag = False
            ret += 1
            continue
        else:
            return ret


print(prime_num(x))

Submission status: Accepted

Solution code:
x = int(input())

def checker(x):
    found = False
    upper = x ** (1/2)

    for i in range(2, round(upper)):
        if x % i == 0:
            found = True
            break

    return False if found == True else True

x -= 1
ok = False

while not ok:
    x += 1
    ok = checker(x)

print(x)

Submission status: Accepted

Solution code:
X=int(input())
flag=1
if X==2:
    flag=0

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

print(X)

Submission status: Accepted

Solution code:
import math
import bisect
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P
n = int(input())
P = eratosthenes(100100)
insert_index = bisect.bisect_left(P,n)
print(P[insert_index])

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

if x % 2 == 0 and x != 2:
    x += 1
    
f = 1
while f:
    f = 0
    y = int(x**0.5)
    for i in range(3, y+1)[::-1]:
        if x / i == x // i:
            x += 2
            f = 1
print(x)

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


X = int(input())

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

Submission status: Accepted

Solution code:
x=int(input())
sosu=0
import math
for a in range(x,10**5+10):
    root_a=int(math.sqrt(a))
    for i in range(2,root_a+1):
        if a % i == 0:
            a=1
    if a!=1:
        sosu=a
        break
print(sosu)

Submission status: Accepted

Solution code:
def task(num):
  num = int(num)
  lst = []

  if num < 2:
    return lst

  if num >= 2:
    lst.append(2)

  for i in range(3, num + 1):       
    if i % 2 == 1:
      switch = True
      for n in range(3, int(i ** 0.5) + 1, 2):
        if i % n == 0:
          switch = False  
          break        
      if switch:
        lst.append(i)
  return lst + [100003]

num=int(input())
lst = task(10**5)
ans = [e for e in lst if e >= num]
print(ans[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X = int(input())

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

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

Submission status: Accepted

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


if r == 2:
    print(2)
else:
    if r % 2 == 0:
        r += 1

    while True:
        if is_prime3(r):
            break
        r += 2

    print(r)

Submission status: Accepted

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############

X = int(input())

def factorize(n):
    i=2
    result=0
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result+=count
        i+=1
    if n>1:
        result += 1
    return result
while factorize(X)>1 :
    X+=1
print(X)

Submission status: Accepted

Solution code:
import math


def is_prime(x):
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    root = int(math.sqrt(x))
    for i in range(2, root):
        if x % i == 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())
flag = True
import numpy as np
if X == 2:
  print(X)
  flag = False
while flag:
  temp_flag = True
  for i in range(int(np.sqrt(X))+1):
    if X % (i + 2) == 0:
      temp_flag = False
      break
  if temp_flag:
    print(X)
    flag = False
    break
  X += 1

Submission status: Accepted

Solution code:
x = int(input())

x_max = 10**5 + 3
is_prime = [True] * (x_max + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, x_max + 1):
    for j in range(2, x_max + 1):
        ij = i*j
        if ij > x_max:
            break
        is_prime[ij] = False

for i, a in enumerate(is_prime):
    if i >= x and a:
        print(i)
        break

Submission status: Accepted

Solution code:
N = 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(len(make_divisors(N)) != 2):
    if N % 2 == 0:
        N += 1
    else:
        N += 2

print(N)

Submission status: Accepted

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


x=X
y=int(math.sqrt(x)//1+1)
if X==2:
    print(2)
else:
    while 1:
      flag=0
      for i in range(y-1):
          if x%(i+2)==0:
              flag=1
              break
      if flag==0:
        print(x)
        break
      x=int(x+1)
      y=int(math.sqrt(x)//1+1)

Submission status: Accepted

Solution code:
import math

def sieve_of_eratosthenes(n):
    prime_nums = []
    lim = n ** 0.5
    data = [i + 1 for i in range(1, n + 1)]
    while True:
        p = data[0]
        if lim <= p:
            return prime_nums + data
        prime_nums.append(p)
        
        data = [d for d in data if d % p != 0]

X = int(input())

prime_nums = sieve_of_eratosthenes(X * 2)
tmp_nums = [prime_num for prime_num in prime_nums if prime_num >= X]
print(tmp_nums[0])