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:
def isprime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  m = int(n ** 0.5) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

x = int(input())

while isprime(x) == False:
    x += 1
  
print(x)

Submission status: Accepted

Solution code:
import math
m=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
for i in range(m,m+1000):
  if is_prime(i):
    print(i)
    break

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
from sys import stdin
input = stdin.readline


class Eratos:
  def __init__(self, n):
    import math

    self.all = []
    self.is_prime = [True]*(n+1)
    self.is_prime[0] = False
    self.is_prime[1] = False

    for i in range(2, int(math.sqrt(n))+1):
      if self.is_prime[i]:
        self.all.append(i)
        j = i + i
        while j <= n:
          self.is_prime[j] = False
          j += i


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

  e = Eratos(X)

  # print(len(e.all))
  for x in range(X, 2*X+1):
    for prime in e.all:
      if x % prime == 0:
        break
    else:
      print(x)
      return


if(__name__ == '__main__'):
  main()

Submission status: Accepted

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

if X==2:
  print(2)
  sys.exit()

for i in range(2,X):
  if X%i==0:
    break
else:
  print(X)
  sys.exit()

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

Submission status: Accepted

Solution code:
import math
import sys
x=int(input())
if x==2:
  print(x)
else:
  while True:
    r=int(math.sqrt(x))
    if all(x%i!=0 for i in range(2,r)):
      print(x)
      sys.exit()
    else:
      x+=1

Submission status: Accepted

Solution code:
import math
x = int(input())
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    
    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(2, math.floor(math.sqrt(num))+1):
        if num % i == 0:
            return False
    # 素数
    return True
  
for i in range(x, 10**6):
    if isPrime(i):
        print(i)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
 
X = int(input())
 
for i in range(X, 100004):
  f = True
  for j in range(2, int(math.sqrt(X))+1):
    if i % j == 0:
      f = False
      break
  if f:
    print(i)
    break

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

Submission status: Accepted

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

Submission status: Accepted

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

if N==2:
    print(N)
    exit()
while True:
    maxi=int(math.sqrt(N))+1
    test=[i for i in range(maxi)]
    for i in range(2,maxi):
        if test[i]!=-1:
            if N%test[i]!=0:
                j=i
                while j<maxi:
                    test[j]=-1
                    j+=i
            else:
                break
        if i==maxi-1:
            print(N)
            exit()
    N+=1

Submission status: Accepted

Solution code:
def is_prime(n):# O(logn)
    if n == 2:
        return 1
    elif n == 1 or n % 2 == 0:
        return 0
    for i in range(3, int(n ** .5) + 1, 2):
        if n % i == 0:
            return 0
    return 1

X = int(input())

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

Submission status: Accepted

Solution code:
import sys
import math

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

def call_is_prime(n):
    return [i for i in range(1,n) if is_prime(i)]


def main():
    
    input = sys.stdin.readline
    x = int(input())
    primes = call_is_prime(x+1000)
    ans = [i for i in primes if i>=x]
    print(min(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math

def isPrime(num):
    if num < 2: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False
    return True

def callIsPrime(input_num):
    numbers = []
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)
    return numbers


def main():
    
    input = sys.stdin.readline
    x = int(input())
    primes = callIsPrime(x+1000)
    ans = [i for i in primes if i>=x]
    print(min(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(N,10**6):
    if is_prime(i):
        print(i)
        exit(0)

Submission status: Accepted

Solution code:
table = [0] * (10**5 + 100)

for i in range(2,10**5 + 100):
    if i != 1:
        for j in range(i * 2,10**5 + 100,i):
            table[j] = 1

n = int(input())

while True:
    if table[n] == 0:
        break
    else:
        n += 1

print(n)

Submission status: Accepted

Solution code:
def prime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
a=int(input())
for i in range(a, 100004):
    if prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
import math
def prime(n):
    limit = math.floor(math.sqrt(n))
    for i in range(2,limit+1):
        if n % i == 0:
            return prime(n+1)
    return n

X = int(input())

print(prime(X))

Submission status: Accepted

Solution code:
from math import sqrt

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

X=int(input())

for x in range(X, 10*X+1):
  if is_prime(x):
    print(x)
    break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n = 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
i = 1
while i > 0:
    if is_prime(n):
        break
    n += 1 
print (n)

Submission status: Accepted

Solution code:
N = int(input())
def is_prime(x):
  if x<=1:return False
  for i in range(2,x):
    if x%i==0 : return False
  return True

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

Submission status: Accepted

Solution code:
x=int(input())

import math
import bisect
#----エラトステネスの篩--------
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
  
s=get_primenumber(100500)

i = bisect.bisect_left(s, x)

print(s[i])

Submission status: Accepted

Solution code:
import math

X = int(input())

for i in range(X, 10**6):
    if i == 1:
        continue
    elif i == 2 or i == 3:
        print(i)
        break
    elif i % 2 == 0 or i % 3 == 0:
        continue
    for j in range(5, math.floor(math.sqrt(i)) + 1, 6):
        if i % j == 0 or i % (j+2) == 0:
            break
    else:
        print(i)
        break

Submission status: Accepted

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

    return True

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

Submission status: Accepted

Solution code:
import math
s = int(input())
if s ==2:
  print(2)
else:
  for i in range(s,2*s):
    if i%2==0:
      continue
    for k in range(3,round(math.sqrt(s))+1,2):
      t = 1
      if i%k ==0:
        t = 0
        break
    if t ==1:
      print(i)
      break

Submission status: Accepted

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

i = 0

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

Submission status: Accepted

Solution code:
from bisect import bisect_right

def eratosthenes(n):
    A = [i for i in range(2, n+1)]
    P = []
    i = 2
    while i**2 <= n:
        prime = min(A)
        P.append(prime)
        j = 0
        while j < len(A):
            if A[j] % prime == 0:
                A.pop(j)
                continue
            j += 1
        i += 1    
    for a in A:
        P.append(a)
    return P
    
x = int(input())
prime_table = eratosthenes(100003)
prime_set = set(prime_table)
if x in prime_set:
    print(x)
else:
    idx = bisect_right(prime_table, x)
    ans = prime_table[idx]
    print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def main():
    def eratosthenes(n):
        A = [i for i in range(2, n+1)]
        P = []
        i = 2
        while i**2 <= n:
            prime = min(A)
            P.append(prime)
            j = 0
            while j < len(A):
                if A[j] % prime == 0:
                    A.pop(j)
                    continue
                j += 1
            i += 1    
        for a in A:
            P.append(a)
        return P

    x = int(input())
    prime_table = eratosthenes(100003)
    idx = bisect_left(prime_table, x)
    ans = prime_table[idx]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def nextPrime(x):

    for i in range(x, x*2):
        a = 0
        for w in range(2, i+1):
            if i%w ==0:
                break
            else:
                a = w
        if i == a + 1:
            return i if x != 2 else 2

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 21   import sympyが最速だが、Atcoderには無い
import math
x = int(input())

#エラトステネスの篩
n = [i for i in range(2,int(math.sqrt(x))+1)]

for i in n:
    for j in n:
        if j % i == 0 and j/i !=1:
            n.remove(j)
            
while x > 0:
    for i in n:
        if x % i == 0:
            break
    else:
        print(x)
        break
    x+=1

Submission status: Accepted

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

Submission status: Accepted

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

def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

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

Submission status: Accepted

Solution code:
import sys

x = int(input())
for i in range(x,10**10+1):
  if i == 2 or i == 3:
    print(i)
    sys.exit()
  else:
    a = int(i**(1/2))
    is_prime = True
    for j in range(2,a+1):
      if i%j == 0:
        is_prime = False
        break
    if is_prime:
      print(i)
      sys.exit()

Submission status: Accepted

Solution code:
ans = int(input())
while True :
    for i in range(2,ans) :
        if ans % i == 0 :
            ans += 1
            break
    else : #breakしなかったときにelseは実行
        print(ans)
        break

Submission status: Accepted

Solution code:
x = int(input())

check = 0

while True:
  for i in range(x, x*2):
    for j in range(2, x*2):
#      print(i, j)
      if i % j == 0 and i != j:
        break
      elif i == j:
        check += 1
#        print("koko")
        break
    if check > 0:
      break
  break

print(i)

Submission status: Accepted

Solution code:
X = int(input())

table = [0] *  100003

for i in range(1,100003+1):
    for j in range(i,100003+1,i):
        table[j-1] += 1

for i in range(X,100003+1):
    if table[i-1] == 2:
        print(i)
        break

Submission status: Accepted

Solution code:
def isPrime(x):
    i = 2
    while i**2 <= x:
        if x % i == 0:
            return False
        i += 1

    return True

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

Submission status: Accepted

Solution code:
x = int(input())


def isPrime(x):
    if x == 2:
        return True
    if x < 2 or x % 2 == 0:
        return False
    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            return False
    return True


while isPrime(x) == False:
    x += 1
print(x)

Submission status: Accepted

Solution code:
from sys import exit

def main():
  X = int(input())
  
  while True:
    for i in range(2, X + 1):
      if i == X:
        print(X)
        exit()
        
      if X % i == 0:
        break    
    
    X += 1
  
  
  
main()

Submission status: Accepted

Solution code:
def is_prime(x):
    if x <= 1:
        return False
    i = 2
    while i*i <= x:
        if x%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:
def isprime(x):
  i = 2
  while i * i <= x:
    if x % i == 0:
      return False
    i  += 1
  return True

x = int(input())
while True:
  if isprime(x):
    print(x)
    break
  x += 1

Submission status: Accepted

Solution code:
N = int(input())

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
out = 0
for i in range(N, 100004):
    if is_prime(i):
        out = i
        break
print(out)

Submission status: Accepted

Solution code:

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

def solve():
    ck = False
    x = X-1
    while not ck:
        x += 1
        ck = is_prime(x)
    print(x)

if __name__ == "__main__":
    X = int(input())
    solve()

Submission status: Accepted

Solution code:
x = int(input())

for j in range(x,100004):
    flg = True
    for i in range(2,j):
        if j % i == 0:
            flg = False
            break
    if flg:
        print(j)
        exit(0)

Submission status: Accepted

Solution code:
import math
X = int(input())
c = 0
N = True
while N:
  for i in range(2,math.ceil((X+c)**.5)+1):
    if (X+c)%i == 0:
      c += 1
      break
  else:
    N = False 
print(X+c if X>2 else 2)

Submission status: Accepted

Solution code:
x = int(input())
def prime(x):
  for i in range(2, int(x**0.5)+1):
    if x%i == 0:
      return False
  return True
for i in range(x, 100003 + 1):
  ans = prime(i)
  if ans:
    break
print(i)

Submission status: Accepted

Solution code:
def SieveOfEratosthenes(n): 
    prime = [True for i in range(10**6 + 1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * 2, 10**6 + 1, p): 
                if prime[i]:    prime[i] = False
        p += 1
    prime[0], prime[1] = False, False
    count = 1
    while(True):
        if prime[p] and p>=n:
            print(p);    break
        p += 1
            
n = int(input())
SieveOfEratosthenes(n)

Submission status: Accepted

Solution code:
import math

x = int(input())

prm_dict = {i: True for i in range(2, 100004)}
for n in range(2, 100004):
    if prm_dict[n]:
        if n >= x:
            break
        for nk in range(n * 2, 100004, n):
            prm_dict[nk] = False
print(n)

Submission status: Accepted

Solution code:
x = int(input())

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

Submission status: Accepted

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

def is_prime(n: int) -> bool:
    if n <= 3: return n > 1
    elif 0 in [n % 2, n % 3]: return False
    i = 5
    while i * i <= n:
        if 0 in [n % i, n % (i+2)]: return False
        i += 6
    return True

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

Submission status: Accepted

Solution code:
#pypyなら通るとか、そんなことないですよね？大人げなく泣き叫びますけど。
x = int(input())
#素数の列を、つくるわよ
prime_list = [2]
for num in range(3, x + 1, 2):
  if all(num % prime != 0 for prime in prime_list):
    prime_list.append(num)

#２は特殊な例よね
if x == prime_list[-1]:
  print(x)
  exit()

#素数は奇数だけ
if x % 2 == 0:
  p = 1
else:
  p = 0
  
#xから、x未満の最大の素数ｘ２の範囲について調べるわ
#素数ｎ<素数ｍ<素数２ｎは常識？
for i in range(x + p, prime_list[-1] * 2 + 1, 2):
  if all(i % j != 0 for j in prime_list):
    print(i)
    exit()

Submission status: Accepted

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


X = int(input())
Ans = primes(500000)

for i in range(X, 500000):
    if i in Ans:
        print(i)
        exit()

Submission status: Accepted

Solution code:
x = int(input())

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

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

Submission status: Accepted

Solution code:
import math
X = int(input())
if X == 2 or X == 3:
    print(X)
    exit()
while True:
    p = True
    for i in range(2, int(math.sqrt(X) + 1)):
        if math.gcd(X, i) > 1:
            p = False
            break
    if p == True:
        print(X)
        exit()
    X += 1

Submission status: Accepted

Solution code:
x = int(input())

# 素数
n = 10 ** 5 + 1000
primes = [True] * (n + 1)
p = 2
while p * p <= n:
    if primes[p]:
        for i in range(p * p, n + 1, p): # p*pスタートでいいのか
            primes[i] = False
    p += 1

primes[0], primes[1] = False, False

while True:
    if primes[x]:
        print(x)
        exit()
    x += 1

Submission status: Accepted

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

for i in range(int(input()), 10 ** 6):
  if is_prime(i) == 0:
    print(i)
    break

Submission status: Accepted

Solution code:
x = int(input())

def is_prim(n):
    if n == 1: return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0: return False
    return True

for i in range(x, 20**5+1):
    if is_prim(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
x = int(input())

A = [0] * (10**6)
for i in range(10**6 - 2):
    j = i + 2
    if A[j] == 0:
        if j >= x:
            break
        else:
            for k in range(10**6 // j):
                A[j * (k)] = 1

print(j)

Submission status: Accepted

Solution code:
X = int(input())
clear = 0
num = X

while True:
    judge = 1
    for i in range(2,int(num/2)+1):
        if num % i != 0:
            continue
        else:
            judge = 0
            break
    
            
        
    if judge == 1:
        break
    else:
        num += 1

if X == 1:
    num = 2
print(num)

Submission status: Accepted

Solution code:
import math
x = int(input())
def prime(n):
  ans = 0
  for i in range(2,int(math.sqrt(n))+1):
    if n % i == 0:
      ans = 1
      break
  return ans
for i in range(x,1000000):
  if prime(i) == 0:
    print(i)
    break

Submission status: Accepted

Solution code:
x = int(input())
n = 2*10**5
table = [2] * (n+1)
table[1] = 1
for i in range(2, n//2+1):
  for j in range(2*i, n+1, i):
    table[j] += 1
for i in range(x, n+1):
  if table[i] == 2:
    print(i)
    exit()

Submission status: Accepted

Solution code:
X = int(input())

pn = []
pn_flg = [0] * 10**6
for i in range(2, 10**6):
    if pn_flg[i] == 1:
        continue
    pn.append(i)
    pn_flg[i] = 1
    for j in range(i, 10**6, i):
        pn_flg[j] = 1

for i in pn:
    if i >= X:
        print(i)
        exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
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
# def isPrime(n):
#     if n < 2:
#     # 2未満は素数でない
#         return False
#     if n == 2:
#     # 2は素数
#         return True
#     for p in range(2, n):
#         if n % p == 0:
#         # nまでの数で割り切れたら素数ではない
#             return False
#   # nまでの数で割り切れなかったら素数
#     return True
X = int(input())
ans = 0
for i in range(X, 10 ** 10):
    if isPrime(i):
        ans = i
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
X = int(input())
if X == 2:
    print(2)
    sys.exit()
if X % 2 == 0:
    X += 1

while True:
    s = int(math.sqrt(X))
    flg = True
    for i in range(3, s, 2):
        if X % i == 0:
            flg = False
            break
    if flg:
        print(X)
        sys.exit()
    else:
        X += 2

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X = int(input())
a = X
while 1:
  f = 1
  for b in range(2, X):
    if a % b == 0:
      f = 0
      break
  if f == 1:
    print(a)
    break
  a += 1

Submission status: Accepted

Solution code:
n = int(input())

primes = [2]

for i in range(3, 10**5+4, 2):
    ind = 0
    while primes[ind] ** 2 <= i:
        if i % primes[ind] == 0:
            break
        ind += 1
    else:
        primes.append(i)
        
print(min([x for x in primes if x >=n]))

Submission status: Accepted

Solution code:
# エラトステネスの篩
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


X = int(input())

N = 10 ** 6
prime_table = make_prime_table(N)
for i in range(X, N + 1):
    if prime_table[i] == i:
        print(i)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

x = int(input())

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

elif x%2 == 0:
    ans = x+1

else:
    ans = x


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

Submission status: Accepted

Solution code:
from math import sqrt

X = int(input())


def is_prime(target):
    max = int(sqrt(target))

    for i in range(2, max+1):
        if target % i == 0:
            return False

    return True


while not is_prime(X):
    X += 1

print(X)

Submission status: Accepted

Solution code:
N = int(input())

n = 100010
prime = []
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, n + 1):
    if is_prime[i]:
        prime.append(i)
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False

for v in prime:
    if v >= N:
        print(v)
        break

Submission status: Accepted

Solution code:
X = int(input())
i = int(X**0.5)

while i >= 2:
    if X % i == 0:
        X += 1
        i = int(X**0.5)
    else:
        i -= 1
        
print(X)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import math
    X = int(input())

    def is_prime(num):
        if num in [1, 2, 3]:
            return True
        else:
            div = 2
            while div <= int(math.sqrt(num)) + 1:
                if num % div == 0:
                    return False
                div += 1
            return True

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

    print(X)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math
 
n = int(input())
 
def trial_division(target):
    dest = int(math.sqrt(target))
 
    for i in range(2,dest):
        if target % i == 0:
            return
    print(target)
    exit(0)

num = 0
while True:
  trial_division(n+num)
  num += 1

Submission status: Accepted

Solution code:
import sys
x = int(input())
MAX = 2 * x
a = [0]*MAX
for i in range(2, MAX, 2):
  a[i - 1] += 1
for i in range(3, MAX+1):
  for j in range(i, MAX+1, i):
    a[j - 1] += 1

for i in range(x, MAX):
  if a[i - 1] == 1:
    print(i)
    sys.exit()

Submission status: Accepted

Solution code:
def prime_table(n):
    prime = [True] * (n+1)
    for i in range(2,n+1):
        if not prime[i]: continue
        for j in range(i+i, n+1, i):
            prime[j] = False
    return prime

X = int(input())
is_prime = prime_table(10**6)
for i in range(X, 10**6):
    if is_prime[i]:
        print(i)
        break

Submission status: Accepted

Solution code:
x=int(input())
p=[True]*(2*x)
p[0]=False
p[1]=False
for i in range(2,x):
    if p[i]:
        for j in range(2*i,2*x,i):
            p[j]=False
ans=x
while p[ans]==False:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math
X = int(input())
count = 0
for i in range(X, 100004):
    search_end = math.ceil(math.sqrt(i))
    for j in range(2, search_end+1):
        if i % j == 0:
            count = 1
            break
    if count == 0 or (count == 1 and i == j):
        print(i)
        break
    count = 0

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
99992
'''

def sieve(x):
	prime = [1]*(2*x+1)
	for i in range(2,int(sqrt(2*x+1))+1):
		zz = 2
		while(i*zz <= 2*x):
			prime[i*zz] = 0
			zz += 1
	prime[0] = prime[1] = 0
	return prime

def solve(x):
	prime = sieve(x)
	for i in range(x,len(prime)):
		if(prime[i]):
			return i

N = int(stdin.readline())
ans = solve(N)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import math
    n = 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:
        flg = is_prime(n)
        if flg is False:
          n += 1
        else:
          print(n)
          exit()
resolve()

Submission status: Accepted

Solution code:
import math
def judge(n):
    
    num=int(math.sqrt(n)//1)
    for i in range(2,num+1):
        if n%i==0:
            return False
    return True
x=int(input())
for i in range(x,10**5+4):
    if judge(i):
        print(i)
        break

Submission status: Accepted

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

def prime_judge(n):
    m=int(sqrt(n)//1)
    for i in range(2,m+1):
        if n%i==0:
            return False
    return True

for i in range(x,x+100000):
    if prime_judge(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
def main():
    import math
    x = int(input())
    n = 0
    while n == 0:
        tmp = 0
        #print(int(math.floor(math.sqrt(x)))+1)
        for i in range(2, int(math.floor(math.sqrt(x)))+1):
            if x % i == 0:
                tmp += 1
                break
        if tmp == 0:
            print(x)
            exit()
        x += 1
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2020/07/01
# AtCoder Beginner Contest 149 - C

# Input
x = int(input())
slist = [0] * 100005

for i in range(2, 100000):
    if slist[i] == 0:
        j = i + i
        while(j < 100004):
            slist[j] = 1
            j = j + i

sidx = x
while(x < 100004):
    if slist[x] == 0:
        ans = x
        break
    x = x + 1

# Output
print(ans)

Submission status: Accepted

Solution code:
x = int(input())

bu = [False]*2*10**5

cur = 2

while cur<x or bu[cur]:
    if not bu[cur]:
        bu[::cur] = [True] * len(bu[::cur])
    cur += 1

print(cur)