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

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

f = (nextPrime(num))

if (len(f) != 2): 
  while (len(f) != 2): 
    num += 1
    f = nextPrime(num)
print (num)

Submission status: Accepted

Solution code:
a = int(input())

i = 2
while i < a:
    if a % i == 0:
        a = a + 1
        i = 2
    else:
        i = i + 1
print(a)

Submission status: Accepted

Solution code:
import math


def trial_division(target):
    dest = int(math.sqrt(target))

    for i in range(2, dest):
        if target % i == 0:
            # print(str(target) + ' is comp')
            return False
    # print(str(target) + ' is prime')
    return True


x = int(input())
pn = 2
while True:
    if trial_division(pn) and x <= pn:
        break
    else:
        pn += 1
print(pn)

Submission status: Accepted

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


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

prime_list = get_primenumber(100000)

left = 0
right = len(prime_list)-1

if X == 2:
    print(int(2))
elif X > 99991:
    print(int(100003))
else:
    while left <= right:
        mid = (left+right) // 2
        if prime_list[mid] == X:
            ans = prime_list[mid]
            break
        elif prime_list[mid] > X:
            if prime_list[mid-1] < X:
                ans = prime_list[mid]
                break
            else:
                right = mid - 1
        else:
            if prime_list[mid+1] > X:
                ans = prime_list[mid+1]
                break
            else:
                left = mid + 1

    print(int(ans))

Submission status: Accepted

Solution code:
#--import&define---------------------
import math
import sys
input = sys.stdin.readline
def yes():
    print("Yes")
def no():
    print("No")

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
#--以下解答---------------------------------
x = int(input())
prime_list = primes(10**6)

i = x
flag = True
while True:
    if prime_list[i] == True:
        print(i)
        sys.exit()
    i += 1

Submission status: Accepted

Solution code:
x = int(input())
ans = 1
while ans<=1:
    for i in range(x-1):
        if i+2 != x and x%(i+2)==0:
            x+=1
            ans = 1
            break
        else:
            ans = x
print(ans)

Submission status: Accepted

Solution code:
p = [0 for _ in range(10**5+11)]
p[0] = 1
p[1] = 1
for i in range(2,10**5+10):
  for j in range(2,10**5+10):
    if 0 <= i*j <= 10**5+10:
      p[i*j] = 1
    else:
      break
n = int(input())
while True:
  if p[n] == 0:
    print(n)
    break
  n += 1

Submission status: Accepted

Solution code:
x = int(input())


def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 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):
            found = True

    return prime


if is_prime(x):
    print(x)
else:
    print(next_prime(x))

Submission status: Accepted

Solution code:
n = 110000
primes = set(range(3, n+1, 2))|set([2])
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*3, n+1, i*2))
primes=list(primes)
primes.sort()
x = int(input())
for i in primes:
  if i >=x:
    print(i)
    break

Submission status: Accepted

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

x = int(input())
a=list(map(int, primes(100003)))
for i in a:
    if x <= i:
        print(i)
        break

Submission status: Accepted

Solution code:
X = int(input())

prime = [True for i in range(10**6)]
prime[0] = False
prime[1] = False

for i in range(2, 10**5+4):
  if prime[i]:
    for j in range(2, (10**5+4)//i + 1):
        prime[i*j] = False
for i, is_prime in enumerate(prime):
  if i >= X and is_prime:
    ret = i
    break
    
print(ret)

Submission status: Accepted

Solution code:
import math

x = int(input())

tmp = int(math.sqrt(x))

if x == 2:
    print(2)

elif x % 2 == 0:
    x += 1
    while True:
        count = 0
        for i in range(3, tmp, 2):
            if x % i == 0:
                x += 2
                count = 1
                break

        if count == 0:
            print(x)
            break

else:
    while True:
        count = 0
        for i in range(3, tmp, 2):
            if x % i == 0:
                x += 2
                count = 1
                break

        if count == 0:
            print(x)
            break

Submission status: Accepted

Solution code:
import math
s=0
number = int(input())
 
def trial_division(target):
    dest = int(math.sqrt(target))
 
    for i in range(2,dest):
        if target % i == 0:
          return(True)
    return(False)

while(trial_division(number)):
   number+=1
print(number)

Submission status: Accepted

Solution code:
#C
x = int(input())
r = int(x**0.5)+1
l = len(str(x)) 
lst = [i for i in range(x,x+r)]

for i in range(2,r):
    for j in lst:
        if j % i == 0:
            lst.remove(j)
print(min(lst))

Submission status: Accepted

Solution code:
X = int(input())

def is_sosu(x):
    for i in range(2, (x//2) + 1, 1):
        if x % i == 0:
            return False
    return True 

chk = True
ans = 0
while(chk):
    if is_sosu(X):
       ans = X
       break
    X += 1
    if is_sosu(X):
        ans = X
        break
print(X)

Submission status: Accepted

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

def chkPrime(N):
  if N == 2 or N == 3:
    return True
  else:
    for i in range(2,int(math.sqrt(N))+1):
      if N % i == 0:
        return False
    else:
      return True

while not chkPrime(N):
  N += 1

print (N)

Submission status: Accepted

Solution code:
X=int(input())
i=2
if X==2:
    print(2)
else:
    while i<=int(X**0.5)+1:
        if X%i==0:
            X+=1
            i=2
        else:
            i+=1
    print(X)

Submission status: Accepted

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

Submission status: Accepted

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

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

i = X
judge = False
while judge == False:
  judge = is_prime(i)
  if judge == True:
    print(i)
    break
  i += 1

Submission status: Accepted

Solution code:
import random

def is_prime3(q, k=50):
    q = abs(q)
    # 計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False

    # n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    # 判定をk回繰り返す
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        # [0,s-1]の範囲すべてをチェック
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

if __name__ == '__main__':
    a = int(input())
    while(not is_prime3(a)):
        a = a+1
    print(a)

Submission status: Accepted

Solution code:
X=int(input())

for Y in range(X,1000000):
  count=0
  for i in range(2,Y+1):
    if Y%i==0:
      count+=1
  if count==1:
    break

   
  
print(Y)