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:
# coding: UTF-8

import numpy as np

X = int(input())


def make_prime(U):
    is_prime = np.zeros(U, np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U ** 0.5) + 1
    for p in range(3, M, 2):
        if is_prime[p]:
            is_prime[p * p :: p + p] = 0
    return is_prime, is_prime.nonzero()[0]


# 'a.nonzero()'で配列の非ゼロ要素のインデックスを取り出せる
# a(a.nonzero())とするとaの非ゼロ要素を取り出せる

_, primes = make_prime(10 ** 5 + 10000)

large = primes[primes >= X]
answer = large.min()
print(answer)

Submission status: Accepted

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

if __name__=="__main__":
    n=int(input())
    cnt=0
    while cnt == 0:
        if is_prime(n):
            cnt+=1
        else:
            n+=1
            continue
    print(n)

Submission status: Accepted

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

n=int(input())
for i in range(n,n+10**5):
  if prime(i)==True:
    print(i)
    break

Submission status: Accepted

Solution code:
n=int(input())
def is_prime(a):
    if a == 1:
        return False
    for i in range(2,int(a**(0.5)+1)):
        if a % i == 0:
            return False
    return True

for i in range(n,10**7):
    if is_prime(i) == True:
        print(i)
        exit()

Submission status: Accepted

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

x = int(input())

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

Submission status: Accepted

Solution code:
from math import sqrt

N = 10 ** 6
p = [True] * (N + 1)
p[0] = False
p[1] = False
n = int(sqrt(N) + 1)

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

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

Submission status: Accepted

Solution code:
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('c1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    X = read_int()
    n = 10 ** 6
    for i in range(X, n):
      is_prime = True     
      for d in range(2, X):
          if i % d == 0:
            is_prime = False
      if is_prime:
        print(i)
        break


main()

Submission status: Accepted

Solution code:
import sys
import bisect
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)
        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list


X = ni()
l = get_primenumber(10 ** 5 +10)
idx = bisect.bisect_left(l, X)
print(l[idx])

Submission status: Accepted

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 or x == 2:
        print(x)
        break
    P.append(int(x**(1/2)+1))
    x += 1

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

def get_smallest_prime(x):
  while True:
    if(is_prime(x)):
      return x
    x+=1

if __name__ == '__main__':
  x=int(input())
  print(str(get_smallest_prime(x)))

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())
while True:
  if is_prime(x):
    print(x)
    break
  x += 1

Submission status: Accepted

Solution code:
X = int(input())
a = [False]*(10**5+100)
l = []
for i in range(2, 10**5+100):
    if not a[i]:
        l.append(i)
        for j in range(i, 10**5+100, i):
            a[j] = True
for n in l:
    if n >= X:
        print(n)
        exit()

Submission status: Accepted

Solution code:
from math import floor, sqrt

X = int(input())

def isprime(n):
    for i in range(2,floor(sqrt(n))+1):
        if n%i == 0:
            return False
    return True

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

Submission status: Accepted

Solution code:
from math import sqrt, floor

def is_prime(x: int) -> bool:
    if x <= 1:
        return False

    for i in range(2, floor(sqrt(x))):
        if x % i == 0:
            return False

    return True


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

Submission status: Accepted

Solution code:
X=int(input())
ans_ama=X
Flag=True
while 1:
    for i in range(2,int(X/2)):
        if X%i==0:
            Flag=False
            break
    if Flag==True:
        ans=X
        break
    Flag=True
    X+=1
print(X)

Submission status: Accepted

Solution code:
X = int(input())
X_i = X 

while X_i >= X:
  ans = 0 
  for i in range(2,int(X_i//(X_i**(1/2))//1)+1):
      if X_i%i == 0:
        ans = 1
        break
      else:
        continue
  if ans != 0:
    X_i += 1
  else:
    print(X_i)
    break

Submission status: Accepted

Solution code:
import math

X = int(input())
prime = False
primecheck = True

if X <= 2:
    prime_num = X

else:
    while prime == False:

        for i in range(2, int(math.sqrt(X))):
            if X % i == 0:
                X += 1
                primecheck = False
                break

        if primecheck == False:
            primecheck = True
        else:
            prime = True
            prime_num = X

print(prime_num)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

X = int(input())

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

print(p)

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

x=int(input())
while is_prime(x) == False:
    x += 1
print(x)

Submission status: Accepted

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

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

for i in range(X,100004):
    t=is_prime(i)
    if(not t):
        continue
    else:
        print(i)
        exit()

Submission status: Accepted

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

while True:
  if prime(s):
    print(s)
    break
  s+=2

Submission status: Accepted

Solution code:
import sys

n = int(input())

while True:
    for i in range(2, int(n**0.5+1)):
        if n % i == 0:
            break
    else:
        print(n)
        sys.exit()

    n = n + 1

Submission status: Accepted

Solution code:
import random

X = int(input())
def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

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

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

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

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

    return True

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

Submission status: Accepted

Solution code:
n = int(input())
const = 10**5+100

a = [i for i in range(2,const+1)]
prime = []

for i in a:
    prime.append(i)

    if i > int(n**0.5):
        break

    a = [j for j in a if j % i != 0]

prime += a

ans = [i for i in a if i >= n][0]

print(ans)

Submission status: Accepted

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

while True:
    for p in range(2, X):
        if X % p == 0:
            break
        elif p == X - 1:
            print(X)
            exit()
    X += 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


x = int(input())

min_prime = 2

for i in range(x, 100005):
    if is_prime(i) is True:
        min_prime = i
        break

print(min_prime)

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

min_prime = 2

for i in range(x, 10 ** 6):
    if is_prime(i) is True:
        min_prime = i
        break

print(min_prime)

Submission status: Accepted

Solution code:

def prime_list_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
def prime_list_eratosthenes_from(n_from, n_to):
    from bisect import bisect_left
    data = prime_list_eratosthenes(n_to)
    i = bisect_left(data, n_from)
    return data[i:]
x = int(input())
d = prime_list_eratosthenes_from(x, 1000000)
print(d[0])

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:
  if is_prime(X):
    print(X)
    break
  X +=1

Submission status: Accepted

Solution code:
X=int(input())

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

    if flag==0:
      break
    else:
      X=X+1
  print(X)

Submission status: Accepted

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

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)!= True):
    X +=1
print(X)

Submission status: Accepted

Solution code:
x = int(input())

while True:
    check = True
    # 素数判定
    for i in range(2, x):
        if x % i == 0:
            check = False
            break
    if check:
        print(x)
        break
    x = x + 1

Submission status: Accepted

Solution code:

X=int(input())
def isp(n):
    for i in range(2,n):
        if n%i==0:return False
    return True

while True:
    if isp(X):
        print(X)
        exit(0)
    X+=1

Submission status: Accepted

Solution code:
from math import sqrt

N = 10 ** 6
p = [True] * (N + 1)
p[0] = False
p[1] = False
n = int(sqrt(N) + 1)

for i1 in range(4, N+1, 2):
  p[i1] = False
for i2 in range(3, n+1, 2):
  if p[i2]:
    for i3 in range(i2+i2, N+1, i2):
      p[i3] = False

X = int(input())
for i4 in range(X, N+1):
  if p[i4]:
    print(i4)
    break

Submission status: Accepted

Solution code:
X=int(input())
b=X**0.5
while any(X%i==0 for i in range(2,int(b)+1)):
  X+=1
else:
  print(X)

Submission status: Accepted

Solution code:
import math


def is_prime(x):
    for i in range(3, math.ceil((x ** 0.5) + 1), 2):
        if x % i == 0:
            return False
    return True

x = int(input())

if x == 2:
    print(2)
else:
    if x % 2 == 0:
        x += 1
    while (not is_prime(x)):
        x += 2
    print(x)

Submission status: Accepted

Solution code:
def isp(x):
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            x += 1
            return isp(x)
        else:
            pass
    return x
n = int(input())
print(isp(n))

Submission status: Accepted

Solution code:
X=int(input())
from math import sqrt
def isp(n):
    for i in range(2,int(sqrt(n))+1):
        if n%i==0:
            return False
    return True
while True:
    if isp(X):
        print(X)
        break
    X+=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

X = int(input())

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

Submission status: Accepted

Solution code:
a = int(input())


for i in range(a,100005):
  flag = 0
  for j in range(2,i):
    if j*j < i:
      if i % j == 0:
        flag = 1
        break
  if flag == 0:
    ans = i
    break
    
print(ans)

Submission status: Accepted

Solution code:
x = int(input())
if x == 2:
  print(2)
  
else:
  var = x
  while True:
    for _ in range(2,var):
      if var%_ != 0:
        ind = True
      else:
        ind = False
        break
    if ind == True:
      break  
    else:
      var+=1  
  print(var)

Submission status: Accepted

Solution code:
X = int(input())

for i in range(X,10**5+10) :
    prime = True
    for t in range(2,X-1) :
        if i%t == 0 :
            prime = False
            break
    if prime == True :
        print(i)
        exit()

Submission status: Accepted

Solution code:
## C
X =int(input())
n=X
while(True):
    Is_Primary=True
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            Is_Primary=False
            break 
    if Is_Primary:
        break
    n+=1

print(n)

Submission status: Accepted

Solution code:
import math
t = int(input())
if t<2:
    print(2)
    exit()
for i in range(t,t+250):
    v = int(math.sqrt(i))
    f=0
    for j in range(2,v+1):
        if i%j==0:
            f=1
            break
    if(f==0):
        print(i)
        break

Submission status: Accepted

Solution code:
n=int(input())
flag=1
for i in range(n,10*n):
  j=2
  flag=1
  while(j<=int(i**(0.5))):
    if(i%j==0):
      flag=0
      break
    j+=1
  if(flag==1):      
    print(i)
    break

Submission status: Accepted

Solution code:
x=int(input())
flag=0
while(1):
    flag=0
    for i in range(2,int(x/2+1)):
        if x%i==0:
            flag=1
            x+=1
            break
    if flag==0:
        print(x)
        break

Submission status: Accepted

Solution code:
import math 

def isPrime(n): 

    if(n <= 1): 
        return False
    if(n <= 3): 
        return True

    if(n % 2 == 0 or n % 3 == 0): 
        return False
      
    for i in range(5,int(math.sqrt(n) + 1), 6):  
        if(n % i == 0 or n % (i + 2) == 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 

N = int(input())
print(nextPrime(N-1))

Submission status: Accepted

Solution code:
a = int(input())
flag = 0
j = 0
while(flag != 1):
    count =0
    temp = a+j
    for i in range(2, temp):
        if(temp %i == 0):
            count +=1
    if(count == 0):
        flag =1
        print(temp)
    j+=1

Submission status: Accepted

Solution code:
a = input()
flag = 0
j = int(a)
k = 1
while(k!=0):
    flag = 0
    for i in range(2, j):
        if(j % i == 0):
            flag = 1
            break;
    if(flag == 1):
        j += 1;
        k = 1
    else:
        k = 0

print (j)

Submission status: Accepted

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

def is_prime(n):
  i = 2
  while i <= math.sqrt(n):
    if n % i == 0:
      return False
    i += 1
  return True

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

Submission status: Accepted

Solution code:
import math
X = int(input())
if X ==2:
    print(2)
else:
    s = 0
    for i in range(X,10**7):
        for j in range(2,math.ceil(i ** 0.5)+1):
            if i % j ==0:
                s += 1
        if s == 0:
            print(i)
            break
        else:
            s = 0

Submission status: Accepted

Solution code:
import math

x = int(input())

# エラトステネスの篩
def Eratosthenes(n):
    if n < 2:
        return None
    prime = [2]
    limit = math.ceil(n**0.5)
    data = list(range(3, n+1, 2))
    p = -1
    while p < limit:
        p = data[0]
        prime.append(p)
        data = [d for d in data if d%p != 0]
    return prime + data


prime = Eratosthenes(10**5+3)
if x in prime:
    print(x)
else:
    import bisect
    min_prime_index = bisect.bisect_right(prime, x)
    print(prime[min_prime_index])

Submission status: Accepted

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

def main():
    N = int(input())
    is_prime = [True for _ in range(2*N)]
    is_prime[0] = is_prime[1] = False
    prime = []
    for i in range(2,2*N):
        if not is_prime[i]:
            continue
        else:
            prime.append(i)
            j = 2*i
            while j < 2*N:
                is_prime[j] = False
                j += i

    index = bisect.bisect_left(prime,N)
    print(prime[index])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
X = int(input())

import math
import sys

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:
    if is_prime(X) == True:
        print(X)
        sys.exit()
    X+=1

Submission status: Accepted

Solution code:
X=int(input())
p=0
for i in range (0,10000):
    if p!=0:
        break
    for j in range (2,X//2):
        if (X+i)%j==0:
            break
        if j==X//2-1:
            p=X+i
print(max(2,p))

Submission status: Accepted

Solution code:
import math


def InS(): return input()


def InL(): return list(map(int, input().split()))


def InI(): return int(input())


X = int(input())


def factors(A):
    a = []
    for i in range(1, A + 1):
        if A % i == 0:
            a.append(i)
    return a


f = (factors(X))

if(len(f) != 2):
    while (len(f) != 2):
        X += 1
        f = factors(X)
    print(X)
else:
    print(X)

Submission status: Accepted

Solution code:
from collections import Counter
x = int(input())

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
  
l = primes(101010)
c = Counter(l)

while c[x] != 1:
  x+=1

print(x)

Submission status: Accepted

Solution code:
import math
N=int(input())
def confirm(n):
    for i in range(int(math.sqrt(n)-1)):
        if n%(i+2)==0:
            return False
    else:
        return True


if confirm(N):
    i=N
else:
    i=N+1
    while True:
        if confirm(i):
            break
        else:
            i+=1

print(i)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x = int(input())

if x==2:
    print(2)
elif x==3:
    print(3)
else:
    while True:
        if x%2==0 or x%3==0:
            x += 1
            continue
        else:
            tmp = 0
            divisor_lst = [1, x]
            for i in range(1,x+1):
                if x%i==0 and i not in divisor_lst:
                    tmp = 1
                    x += 1
                    break
            if tmp==0:
                break
            elif tmp==1:
                continue
    print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def eratosthenes_sieve(n: int):
    """
    エラトステネスの篩を用いてn以下の素数を求める
    """
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

def solve(X: int):
    L = eratosthenes_sieve(200000)
    mn = 0
    for l in L:
        if l >= X:
            mn = l
            break
    print(mn)
    return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
import math

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

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

Submission status: Accepted

Solution code:
import math

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

X = int(input())
x=X

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

print(x)

Submission status: Accepted

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


X = int(input())

while not is_prime(X):
    X += 1

print(X)

Submission status: Accepted

Solution code:
X = int(input())

# 2のケース
if X == 2:
    print(X)
    exit()

# 2 以外のケース
for i in range(X, 10 ** 6):
    cnt = 1
    for j in range(2, i // 2 + 2):
        cnt += 1
        if i % j == 0:
            break
        if cnt == (i // 2 + 1):
            print(i)
            exit()

Submission status: Accepted

Solution code:
import random
from collections import  Counter
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 (0,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

x=int(input())
while(1):
    if is_prime3(x):
        print(x)
        exit()
    else:
        x+=1

Submission status: Accepted

Solution code:
x = int(input())

#def prime number discriminator

def prime_or_not(a):
  b = 0
  i = 2

  if a == 2:
    ans = True
    
  else:
    while i <= a - 1 and b < 1:
      if a % (i)== 0:
        b += 1
        i += 1
      else:
        i += 1
      
      if b >= 1:
        ans = False
      else:
        ans = True

    return ans

ans = 0

if x == 2:
  print(2)
else:
  while ans <1:
    ans += prime_or_not(x)
    x += 1
  print(x - 1)

Submission status: Accepted

Solution code:
X = int(input())

MAGIC_NUMBER = 2

prime = [True] * (X * MAGIC_NUMBER + 1)
prime[0] = False
prime[1] = False

for p in range(2, X + 1):
    if not prime[p]: continue
    p_tmp = p
    while True:
        p_tmp += p
        if p_tmp >= len(prime): break
        prime[p_tmp] = False

# print("#", prime)
for ans in range(X, X * MAGIC_NUMBER + 1):
    if prime[ans]: break

print(ans)

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

x = int(input())

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

Submission status: Accepted

Solution code:
import itertools as it

def next_sosu(x):
  if x%2==0:
    if x==2:
      return x
    else:
      x+=1
  l=[i for i in range(3,x,2)]
  for i in it.count(x,2):
    if len(list(filter(lambda a:i%a==0,l)))==0:
      return i
print(next_sosu(int(input())))

Submission status: Accepted

Solution code:
import math

X = int(input())

check = X
while check <= 200000:

  is_prime = True

  i = 2
  while i <= math.sqrt(check):
    if (check % i == 0):
      is_prime = False
      break
    i += 1

  if (is_prime):
    break

  check += 1

print(check)

Submission status: Accepted

Solution code:
x = int(input())

#√nまでの素数の配列を返す関数
def primes(n):
    if n < 4:
        return []
    else:
        pri = [2]
        k = 3
        while k*k <= n:
            for i in pri:
                if k%i == 0:
                    break
                elif i == pri[-1]:
                    pri.append(k)
            k += 2
        return pri

prime = primes(x)
if x == 2:
    print(2)
else:
    x = (x//2)*2 + 1
    while True:
        flag = True
        for i in prime:
            if x%i == 0:
                x += 2
                flag = False
                break
        if flag:
            break
    print(x)

Submission status: Accepted

Solution code:
import math

N = int(input())

def is_prime(x):
    c = 2
    while c < math.sqrt(x):
        if x % c == 0:
            return False
        c += 1
    return True

if N % 2 == 0 and N > 2:
    N += 1

while True:
    if is_prime(N):
        break
    N += 2

print(N)

Submission status: Accepted

Solution code:
import math

def is_prime(n):
    if n <= 0: return None
    if n == 1: return False
    sup = math.floor(pow(n,1/2))
    for i in range(2,sup+1):
        if n % i == 0:
            return False
    return True

X = int(input())
for x in range(X, 2 * X + 1):
    if is_prime(x):
        print(x)
        break

Submission status: Accepted

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

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:
x = int(input())
y = x
while True:
  if all([y%i!=0 for i in range(2,int(y**0.5+1))]):
    break
  else:
    y += 1
print(y)

Submission status: Accepted

Solution code:
def prime(x):
    n = 2
    while(n * n <= x):
        if(x % n ==0):
            return False
        n += 1
    return True      
    
x = int(input())
while(prime(x)!=True):
    x += 1
    
print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
def is_not_prime(n):
    for i in range(2, math.ceil(n**0.5)):
        if n % i == 0:
            return True
    else:
        print(n)
        return False

X = int(input())
while is_not_prime(X):
    X += 1

Submission status: Accepted

Solution code:
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

arr = seachPrimeNum(10**5 + 99999)
x = int(input())

for i in range(len(arr)):
    if arr[i] >= x:
        print(arr[i])
        break

Submission status: Accepted

Solution code:
from math import sqrt

X = int(input())
p = -1

if X == 1 or X == 2:
    print(X)
    exit()

for i in range(X, 10**10):
    if i % 6 == 1 or i % 6 == 5:
        isPrime = True
        for j in range(2, int(sqrt(i)) + 1):
            if i % j == 0:
                isPrime = False
                break
            else:
                continue
        if isPrime == True:
            p = i
            break
    else:
        continue
print(p)

Submission status: Accepted

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

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

x = int(input())
while 0<1:
  if is_prime(x):
    print(x)
    break
  else:
    x+=1

Submission status: Accepted

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

X = int(input())
while is_prime(X) == False:
    X = X+1
print(X)

Submission status: Accepted

Solution code:
N = int(input())

prime = N

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

while not isPrime(prime):
  prime = prime + 1
  
print(prime)