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

def isPrime(n):
    for j in range(2,int(n**0.5)):
        if n % j == 0:
            return False
    return True

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

Submission status: Accepted

Solution code:
import sys

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

x=int(input())

while(1):
    if isPrime(x):
        print(x)
        sys.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())
while is_prime(X)==False:
  X=X+1
print(X)

Submission status: Accepted

Solution code:
X = int(input())

def sqrt(x):
    last_guess=x/2
    while True:
        guess=(last_guess+x/last_guess)/2
        if abs(guess-last_guess)<.000001:
            break
        last_guess=guess
    return guess

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

def next_prime(N): 
    if (N <= 1): 
        return 2
  
    prime = N 
    found = False
    while(not found): 
        prime = prime + 1
  
        if(is_prime(prime) == True): 
            found = True
  
    return prime 

if 1==X:
    print(2)
    exit(0)
print(next_prime(X-1))

Submission status: Accepted

Solution code:
import sys
n = int(input())
for i in range(n,2*n):
    chk = True
    for j in range(2,n):
        if i%j==0:
            chk=False
    if chk==True:
        print(i)
        sys.exit()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math
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 = int(input())
K = 0
li = get_primenumber(100010)
for i in range(len(li)) :
    if li[i] >= X :
        K = li[i]
        break
print(K)

Submission status: Accepted

Solution code:
n = 200000
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)
x=int(input())
for i in primes:
    if i>=x:
        print(i)
        exit()

Submission status: Accepted

Solution code:
X=int(input())
mx=100100
p=[True]*(mx+10)
p[0]=p[1]=False
for i in range(2,mx+1):
  if p[i]==True:
    for j in range(i*i,mx+1,i):
      p[j]=False
A=[]
for i in range(1,mx+1):
  if p[i]==True:
    A.append(i)

i=0
while X>A[i]:
  i=i+1
print(A[i])

Submission status: Accepted

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

n=int(input())
for i in range(n,10**6+100):
    if is_prime2(i) is True:
        print(i)
        exit()

Submission status: Accepted

Solution code:
x = int(input())

ans = 0
max = 100005
prime_list = []
is_prime = [True for _ in range(max)]
is_prime[0] = False
is_prime[1] = False

for i in range(2, max):
    if is_prime[i]:
        if i >= x:
            #print(is_prime)
            ans = i
            break
        for j in range(2*i, max, i):
            is_prime[j] = False

print(ans)

Submission status: Accepted

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

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

    return True

while 1:
    if is_prime(a) == False:
        a = a+1
    else:
        break

print(a)

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 int_input():
    return int(input())
  
int_input = int_input()
while True:
  if is_prime(int_input):
    print(int_input)
    break
  else:
    int_input += 1

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
 
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())
 
for i in range(X, 1000001):
  if is_prime(i):
    break
    
print(i)

Submission status: Accepted

Solution code:
n = int(input())
flag = False
def isPrime(n):
  if n == 2:
    # 2は素数
    return True
  for p in range(2, int(n **0.5) + 1):
      if n % p == 0:
        return False
  return True
n -= 1
while not(flag):
    n += 1
    flag = isPrime(n)
print(n)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as  np
import math

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


x = int(input())
data = get_sieve_of_eratosthenes(x+100)
data = np.array(data)
indices = np.where(data >= x)[0]
# print(indices)
print(data[indices[0]])

Submission status: Accepted

Solution code:
X = int(input())

def twari(x):
    if x == 2 or x == 3:
        is_p = 1
    else:
        rootx = x**(1/2)
        marootx = int(x // rootx)
    #     print(rootx,marootx)

        prime_list = [x for x in range(3,marootx+1,2) if x % 3 != 0]
        prime_list = [2,3] + prime_list

        is_p = 1

        for p in prime_list:
    #         print(p)
            if x % p == 0:
                is_p = 0
                break
    return(is_p)
    
count = 0
isp = 0
while isp == 0:
    isp = twari(X)
    if isp == 1:
        break
    else:
        X += 1

print(X)

Submission status: Accepted

Solution code:
import math


def isPrime(k):
    if k % 2 == 0 and k != 2:
        return False

    limitDivisor = math.floor(math.sqrt(k)) + 1
    for divisor in range(2, limitDivisor):
        if k % divisor == 0:
            return False

    return k


x = int(input())
limitX = 2 * x - 1

for i in range(x, limitX):
    if isPrime(i):
        print(i)
        exit()

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

print(X)

Submission status: Accepted

Solution code:
import math
x = int(input())
flag = 0
out = 0

for i in range(100000):
  t = x + i
  tr = int(math.sqrt(t)) + 1
  for j in range(2, tr):
    if t % j == 0:
      flag = 1
      break
  if flag == 0:
    out = t
    break
  else:
    flag = 0

if flag == 1:
  if x == 2 or x == 3 or x == 5 or x == 7:
    out = t
print(out)

Submission status: Accepted

Solution code:
import numpy as np

X=int(input())

#エラトステネスの篩
def get_next_primenumber(number):
    x=number
    number=number*2
    prime_list = []
    search_list = list(range(2,number+1))
    answer=2
    while True:
      if search_list[0] > np.sqrt(number):
        prime_list.extend(search_list)
        break
      else:
        head_num = search_list[0]
        prime_list.append(head_num)
        search_list.pop(0)
        search_list = [num for num in search_list if num % head_num != 0]
    
    plist=prime_list[::-1]
    for i in range(1,len(plist)):
        if(x>plist[i]):
            answer=plist[i-1]
            break

    return answer


print(get_next_primenumber(X))

Submission status: Accepted

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

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

for i in range(10000):

    for j in range(2, int(x/2)+1):
        if (x%j == 0):
            break

        if (j == int(x/2)):
            print(x)
            sys.exit()

    x += 1

Submission status: Accepted

Solution code:
x = int(input())
if x == 2:
    print(2)
    exit()
if x % 2 == 0:
    x += 1
while True:
    flag = False
    i = 3
    while i <= x**0.5:
        if x % i == 0:
            flag = True
            break
        i += 2
    if flag:
        x += 2
    else:
        print(x)
        break

Submission status: Accepted

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

#output
import math
M = int(math.sqrt(X))

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

while not is_prime(X):
    X += 1

print(X)

Submission status: Accepted

Solution code:
primes = [2]

x = int(input())
for i in range(3, x * 2):
    is_p = True
    for p in primes:
        if i < p * p:
            break
        if i % p == 0:
            is_p = False
            break
    if is_p:
        primes.append(i)

print([i for i in primes if i >= x][0])

Submission status: Accepted

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

check = True

c = X
while check:
    for x in range(2, c):
        if c % x == 0:
            check = False


            c += 1
            break

    if check:
        print(c)
        sys.exit()

    else:
        check = True

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

X = int(read())

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, is_prime.nonzero()[0]

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

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

Submission status: Accepted

Solution code:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

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


X = int(input())


#d = get_sieve_of_eratosthenes(X+10000)
d = seachPrimeNum(X+1000)
#print(d)
for k,sd in enumerate(d):
    if sd>=X:
        nextprime=d[k]
        break

print(nextprime)

#for xx in range(x,x+1000):

Submission status: Accepted

Solution code:
import math

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

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

print(x)

Submission status: Accepted

Solution code:
x = int(input())
pf = [True]*(10**6)
for i in range(10**6):
    if i == 0 or i == 1:
        pf[i] = False
        continue
    for j in range(2, (10**6-2)//i):
        pf[j*i] = False
for i in range(10**6):
    if pf[i] and i >= x:
        print(i)
        exit()

Submission status: Accepted

Solution code:
n = int(input())
flag = False
flag2 = True
while flag2:
    for p in range(2, n):
        if n % p == 0:
            flag = True
        if flag:
            break
    if flag:
        n += 1
        flag = False
    else:
        print(n)
        flag2 = False

Submission status: Accepted

Solution code:
import math
x = int(input())
ans = x
def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  if n % 2 == 0:
    # ２ではない偶数は素数ではない
    return False
  
  # nの半分まで計算する範囲を絞る
  m = math.floor(n / 2) + 1
  for p in range(3, m, 2): # 奇数だけ計算する
      if n % p == 0:
        return False
  return True

for i in range(x):
    if isPrime(x+i):
        print(x+i)
        break

Submission status: Accepted

Solution code:
def sqrt(x):
    return x ** (.5)

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

X = int(input())

if is_prime(X):
    print(X)
    exit()
if X % 2 == 0:
    X += 1
while (1):
    if is_prime(X):
        print(X)
        break
    X += 2

Submission status: Accepted

Solution code:
x = int(input())
if x%2 == 0 and x != 2:
    x += 1
if x == 2:
    print(x)
def judge(x):
    for i in range(3,int(x**(1/2))+1,2):
        if x%i == 0:
            return False
    return True

if x >= 3:
    while True:
        if judge(x):
            print(x)
            break
        else:
            x += 2

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import fractions

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

Submission status: Accepted

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

        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

while True:
     if is_prime3(n):
         break
     n+=1
print(n)

Submission status: Accepted

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

def p(X):
    sqr = math.floor(math.sqrt(X))
    for i in range(2,sqr):
        if X % i == 0:
            return False
    return True

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

Submission status: Accepted

Solution code:
x=int(input())
l=[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313]
for i in range(1000):
    m=0
    for j in range(len(l)):
        if (x+i)%l[j]==0 and l[j]!=x+i:
            break
        elif l[j]==x+i:
            m=len(l)
            break
        else:
            m+=1
    if m==len(l):
        break
    else:
        continue
    
print(x+i)

Submission status: Accepted

Solution code:
import math

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, 1000000)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
        
x = int(input())
ans = get_sieve_of_eratosthenes(x)
for i in ans:
  if i >= x:
    print(i)
    break

Submission status: Accepted

Solution code:
def check(num):
    for i in range(num-1,1,-1):
        if(num%i==0):
            return False
    return True
ans = 0
X = int(input())
N = 10**5
for i in range(N):
    ans = X + i
    if(check(ans)):
        break

print(ans)

Submission status: Accepted

Solution code:
X = int(input())

import math

while True:
    be_prime = True
    
    for i in range(2, int(math.sqrt(X))+1):
        if X % i == 0: 
            be_prime = False
    
    if be_prime:
        print(X)
        exit(0)
    else:
        X += 1

Submission status: Accepted

Solution code:
def chkprime(num):
    isprime = False
    for i in range(2, num):
        if num % i == 0:
            isprime = True
            continue
        else:
            pass
    return(isprime)

a = int(input())
while True:
    if chkprime(a):
        a += 1
    else:
        break

print(a)