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: Time Limit Exceeded

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:
            if i == int(x**0.5):
                print(x)
                exit()

Submission status: Time Limit Exceeded

Solution code:
x = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
x = int(input())

if x==2 or x==3:
    print(x)
    exit()

lst = [i for i in range(x,x*2+2)]

max = int(x**0.5)
for i in range(2,max+1):
    for j in lst:
        if j%i==0:
            lst.remove(j)

print(lst[0])

Submission status: Time Limit Exceeded

Solution code:

import math
x=int(input())
serach_number = 200000


def sieve_of_eratosthenes(target):
    k=0
    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)
        if num_min>=x:
            k=1
        if k==1:
            print(num_min)
            return
        i = 0

        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1




sieve_of_eratosthenes(serach_number)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
prime_table = []

def judge(n):
    for i in prime_table:
        if n%i == 0:
            return False
    prime_table.append(n)
    return True

num = 1
p = True
while p == True:
    num += 1
    if judge(num) == True:
        if num >= x:
            p = False

print(num)

Submission status: Time Limit Exceeded

Solution code:
L=[i for i in range(2,10**5)]
X=int(input())
while X > L[0]:
  a=L[0]
  for l in L:
    if not l%a:
      L.remove(l)
print(L[0])

Submission status: Time Limit Exceeded

Solution code:
L=[i for i in range(2,10**5)]
X=int(input())
while X > L[0]:
  L=list(filter(lambda x: x & L[0], L))
print(L[0])

Submission status: Time Limit Exceeded

Solution code:
import math

X = int(input())
X_sqrt = int(math.sqrt(X))

flag = 0
while flag == 0:
  if X >= 10**5 + 3:
    print("big")
    break
    
  flag = 1
  for i in range(2, X_sqrt):
    if X % i == 0:
      flag = 0
      break
  
  if flag == 1:
    print(X)
    break

Submission status: Time Limit Exceeded

Solution code:
import math

X = int(input())
X_sqrt = int(math.sqrt(X))

flag = 0
while flag == 0:
  if X >= 10**6:
    print("big")
    break
    
  flag = 1
  for i in range(2, X_sqrt):
    if X % i == 0:
      flag = 0
      break
  
  if flag == 1:
    print(X)
    break

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
rx = int(x**(1/2)) + 1
P = [2] + [2*i+1 for i in range(1, rx//2)]
while True:
    flag = True
    for i in P:
        if x % i == 0:
            flag = False
            break
    if flag:
        print(x)
        break 
    if P[-1] != int(x**(1/2)):
        P.append(int(x**(1/2)))
    x += 1

Submission status: Time Limit Exceeded

Solution code:
def prime(x):
    if x == 2:
        return 2
    num_list = list(range(3, (10 ** 5) * 2, 2))
    n = 3
    while (n < x):        
        num_list = [num for num in num_list if ((num % n) != 0)]
        n = num_list.pop(0)
    return n

x = int(input())
print(prime(x))

Submission status: Time Limit Exceeded

Solution code:
y = int(input())
def satoki(x):
    if x == 1 or x == 2:
        return 2
        


    primes = [2]
    i = 3
    while True:
        isDivisible = False
        for prime in primes:
            if i % prime == 0:
                isDivisible = True
        if not isDivisible:
            primes.append(i)
            if i >= x:
                break
        i+=2

    return primes[-1]

print(satoki(y))

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
primes = []
i = 2
while True:
    isDivisible = False
    for prime in primes:
        if i % prime == 0:
            isDivisible = True
    if not isDivisible:
        primes.append(i)
        if i >= x:
            break
    i+=1

print(primes[-1])

Submission status: Time Limit Exceeded

Solution code:
X = int(input())
A = []
for a in range(2, 10**5):
    for x in range(2, 10**5):
        if a // x != 0 and a>=X and a>=2:
            A.append(a)
print(A[0])

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
i = 11

if n == 8 or n ==9:
  print(11)
  i = 0
elif n == 2 or n== 3 or n == 5 or n == 7:
  print(n)
  i = 0
elif n <= 7 and n%2 == 0:
  print(n+1)
  i = 0

while i != 0:
  j = 3
  js = int(math.sqrt(i))
  while j <= js:
    if  i%j == 0:
      break
    elif j == js or j == js-1:
      print(i)
      break
      i = 0
    else:
      if j%2 == 0:
        j += 1
      else:
        j += 2
  if i%2 == 0:
    i += 1
  else:
    i += 2

Submission status: Time Limit Exceeded

Solution code:
X=int(input())
if X==2:
    pass 
else:
    for _ in range(1,X):
        for i in range(2,X):
            if (X)%i ==0:
                X+=1
            else:
                continue
print(X)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
n = int(input())
def eratosthenes(n):
    prime = [2]
    i = 2
    while prime[-1] < n:
        i += 1
        prime_bit = 0
        for div in prime:
            if i % div == 0: 
                break
            if div == prime[-1]: prime_bit = 1
        if prime_bit: prime.append(i)
        """for j in range(2,math.ceil(i**1/2)+1): #２だけ特別扱いしないといけない
            if i % j == 0: break
            if j == math.ceil(i**1/2): 
                prime.append(i)"""
    return prime
prime = eratosthenes(n)
print(prime[-1])

Submission status: Time Limit Exceeded

Solution code:
X = int(input())
def price(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 1:
  if price(X):
    print(X)
  else:
    X += 1

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
N = int(input())

L = [v for v in range(2, 2*N)]

while L:
    cur = L.pop(0)
    L = list(filter(lambda x: x % cur != 0, L))
    if cur >= N:
        print(cur)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import math

for i in range(int(input()),100004):
  ri = math.floor(i**0.5) + 1
  for j in range(ri):
    for k in range(ri,i):
      if j*k == i:
        break
    else:
      continue
    break
  else:
    print(i)
    break

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
while(x%i<1 for i in range(2,x)):
  x+=1
print(x)

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
while(x%i<1 for i in range(2,x)):
  x+=1

print(x)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
num = int(input())

while True:
    for i in range(1,num+1):
        count =0
        for j in range(i):
             if i%(j+1) == 0:
                count +=1
    if count ==2:
        print(num)
        exit()
    else:
        num += 1

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
val = []
prime = []
for i in range(2,100000):
    val.append(i)
while len(val) != 0:
    prime.append(val[0])
    val = [i for i in val if i % val[0] != 0]
#print(prime)
#print(val)

ans = 2
for i in prime:
    if i >= x:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

n = 10**5+10

x = int(input())

nums = [1 for i in range(n)]

for i in range(2, n):
  if nums[i] == 0:
    continue
  if (i>=x):
    print(i)
    exit()
  for j in range(i+1, n):
    if j%i==0:
      nums[j] = 0

Submission status: Time Limit Exceeded

Solution code:
import sys
X = int(input())
P = [2]
if X == 2:
    print(2)

    sys.exit()
for i in range(3, 10**6):
    for l in range(len(P)):
        if i % P[l] == 0:
            break
        elif l == len(P)-1 and i >= X:
            print(i)
            sys.exit()
        elif l == len(P)-1:
            P.append(i)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
num = 2

# 素数リスト
prime_list = []

while True:
    # 取り出した数字が素数リストの要素で割れなければ素数リストに追加する
    if all(num % prime != 0 for prime in prime_list):
        prime_list.append(num)
        if num >= x:
            break
    num += 1

print(num)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
  prime_table = [2]
  for i in range(3,n+1):
    f = 1
    for j in prime_table[:bisect.bisect_right(prime_table,int(i**0.5))]:
      if i % j == 0:
        f = 0
        break
    if f:
      prime_table.append(i)
  return prime_table

import bisect
n = int(input())
prime_table = prime(10**6)
print(prime_table[bisect.bisect_left(prime_table,n)])

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
s={2}
if x==2:
	print(2)
else:
	for i in range(3,10**6):
		if all(i%j!=0 for j in s):
			s.add(i)
			if i>=x:
				print(i)
				break

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
 
@lru_cache(maxsize=100000)
def n_th_prime(n):
    if n == 0:
        return 2
    z = n_th_prime(n-1) + 1
    while True:
        for i in range(n):
            if z % n_th_prime(i) == 0:
                break
        else: return(z)
        z += 1

x = int(input())

k=0
while True:
    a = n_th_prime(k)
    if x > a:
        k += 1
    else:
        print(a)
        break

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
 
for val in range(x, x**1000000000) :
	if x ==2 :
		print(x)
		break
	elif ((2** val) % val) == 2 :
		print (val)
		break
	else :
		continue

Submission status: Time Limit Exceeded

Solution code:
# ABC149C - Next Prime
def is_prime(n: int) -> bool:
    """
    Evaluate whether a number is prime or not.

    Args:
        n: a number to evaluate

    Returns: whether n is prime or not
    """
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            return False
    return True


def main():
    N = int(input())
    while not is_prime(N):
        N += 2
    print(N)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MAX_X = 10 ** 5
buffer = 10 ** 3
prime_flags = [1 for _ in range(MAX_X + buffer)]

for i in range(MAX_X + buffer):
  num = i
  while num < MAX_X + buffer:
    num += i
    prime_flags[num] = 0

X = int(input().strip())
for i, flag in enumerate(prime_flags[X:]):
  if flag == 1:
    print(X + i)
    break

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def com(_x):
    _flg = 1
    mx  = int(_x**0.5)
    for i in range(2, mx+1):
        if _x % i == 0:
            _flg = 0
            break
    return _flg


x = int(input())
flg = 0
while flg == 0:
    #print("a")
    _flg = 1
    mx  = int(x**0.5)
    for i in range(2, mx+1):
        if x % i == 0:
            _flg = 0
            break
    fig = _flg
    if flg == 0:
        x+=1
print(x)

Submission status: Time Limit Exceeded

Solution code:
prims = list()

prims.append(2)

base = int(input())

def _is_prim(n):
  global prims
  for p in prims:
    if n == p:
      return True
    elif n % p == 0:
      return False
  
  return True

# 入力値までの素数を作る
for n in range(base):
  if n < 2:
    continue
  elif n % 2 == 0:
    continue
  elif _is_prim(n):
    prims.append(n)

# 作った素数値で。。。
while not _is_prim(base):
  base += 1

print(base)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan  4 16:42:19 2020

@author: masat
"""

X = int(input())

p_list = [2]

if X == 2:
    pass
else:
    tobetest_list = [2*i+3 for i in range(6 * 10**4)]
    for i in range(6 * 10**4):
        p_list.append(tobetest_list[0])
        #追加したtobetest_list[0]の倍数をtobetest_list[0]から除く
        k_list = []
        for k in tobetest_list:
            if k % tobetest_list[0] != 0:
                k_list.append(k)
            else:
                pass
        tobetest_list = k_list
        if p_list[-1] >= X:
            break
        else:
            pass
    
print(p_list[-1])

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
prime = []
for i in range(2,2*x):
    prime_check = 0
    for j in prime:
        if i % j == 0:
            prime_check = 1
            break
    if prime_check == 0:
        if i >= x:
            ans = i
            break
        else:
            prime.append(i)
print(ans)

Submission status: Time Limit Exceeded

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

x = int(input())
num = [i for i in range(2, 100010)]
#print(num)

np_x = np.array(num)

for i in range(2, 100010):
    b = np.logical_or(np_x == i, np_x%i != 0)
    np_x = np_x[b]
#print(np_x)

ans = np_x[np_x >= x]
#print(ans)
print(ans[0])

Submission status: Time Limit Exceeded

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

num = 3
ps = [2]
while 1:
  flag = True
  for p in ps:
    if num%p == 0:
      flag = False
      break
  if flag:
    ps.append(num)
    if num>=X:
      print(num)
      exit()
  num += 1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
X =int(input())

if X == 2:
    print(X)

else:
    s = np.array([2])
    
    for i in range(2, 10**5 + 3):
        res = True
        for j in s:
            if (i % j) == 0:
                res = False
                break
        
        if res == True:
            s = np.append(s, i)
            if i >= X:
                print(i)
                break

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# Next Prime
import numpy as np

# input
X = int(input())

# solve
primes = np.array([1])
numbers = np.array(list(range(2, 10**5 + 1)))
while len(numbers) > 0 and max(primes) < X:
    primes = np.append(primes, numbers[0])
    numbers = numbers[numbers % numbers[0] != 0]

res = int(max(primes))

# output
print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
nn=int(input())
n=10**5+1
a=[0]*n
a[1]=0
ans=1
pre=1
if nn==1:
    print(1)
else:
        
    for i in range(2,n):
        if a[i]==0:
    
            if i>=nn:
                print(i)
                break
            pre =ans
            ans=i
            
            for j in range(i+1,n):
                #print(i,j,a[j])
                if j%i==0:
                    a[j]=1
                    #print("asdf",i,j,a[j])
    """
    for i in range(nn,n):
        if a[i]==0:
            print(i)
    
            
                    
                    
    """