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

for i in range(X,10**6):
  Flag=True
  for j in range(2,X):
    if i%j==0:
      Flag=False
      break
  if Flag==True:
    print(i)
    break

Submission status: Accepted

Solution code:
num = int(input())

prime = True
while True:
    prime = True
    for i in range(2,num//2):
        if (num%i==0):
            prime = False
            num+=1
    if prime:
        print(num)
        break

Submission status: Accepted

Solution code:
import math
import sys

def judgement(num):
	dest = int(math.sqrt(num))
	for i in range(2,dest):
		if num % i == 0:
			return False
	return True
X = int(input())

while True:
	if judgement(X) == False:
		X += 1
	else:
		print(X)
		sys.exit()

Submission status: Accepted

Solution code:
def isPrime(n) : 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True

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

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

for i in range(x, x +1000):
    if is_prime(i) == True:
        print(i)
        break

Submission status: Accepted

Solution code:
def is_prime(n):
    factors = 0
    for i in range(1, n+1):
        if n % i == 0:
            factors += 1

        if (factors > 2):
            break

    return factors == 2


X = int(input())

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

    print(X)

Submission status: Accepted

Solution code:
def prime_sieve(N):
    if N < 2:
        return []
    search_list = list(range(2, N + 1))
    prime_list = []
    while search_list[0] <= N ** 0.5:
        prime_list.append(search_list[0])
        tmp = search_list[0]
        search_list = [i for i in search_list if i % tmp != 0]
    prime_list.extend(search_list)
    return prime_list


A = prime_sieve(100005)
X = int(input())
for p in A:
    if p >= X:
        print(p)
        break

Submission status: Accepted

Solution code:
X=int(input())

def isPrime(n):
  if n==2:
    return True
  for p in range(2,n):
    if n%p==0:
      return False
    elif p*p>n:
      break
  return True

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

Submission status: Accepted

Solution code:
x=int(input())
ps=[2]
i=3
while ps[-1] < x:
    for p in ps:
        if i%p==0:
            break
        elif i<p**2:
            ps.append(i)
            break
    i+=2
print(ps[-1])

Submission status: Accepted

Solution code:
import math
x = int(input())
if x==2:
    print(2)
else:
    for i in range(x, 100004):
        if i%2==0:
            continue
        for j in range(3, int(math.sqrt(i)+1)):
            if i%j==0:
                break
        else:
            print(i)
            break

Submission status: Accepted

Solution code:
import math

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

if __name__ == "__main__":
  x = int(input())
  flag = False
  while flag == False:
    if isPrime(x) == True:
      flag = True
      print(x)
    else:
      x = x + 1

Submission status: Accepted

Solution code:
n = int(input()) 

import math
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

if(is_prime(n)):
    print(n)
else:
    while(is_prime(n) == False):
        n = n + 1
        is_prime(n)
    print(n)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
x = int(input())
i = 2
INF = 100000000
while (i <= x):
    if (x%i == 0 and x != i):
        break
    if (x % i == 0 and x == i):
        print(x)
        sys.exit()
    i += 1

while (x < INF):
    i = 2
    while(i <= x):
        if (i % 2 == 0):
            i += 1
            continue

        if (x % 2 == 0):
            x += 1
            continue

        if (x % i == 0 and x != i):
            x += 1
            break

        if (x % i == 0 and x == i):
            print(x)
            sys.exit()

        else:
            i += 2

    x += 1

Submission status: Accepted

Solution code:
num = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 100, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 200, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 300, 293, 307, 311, 313, 317, 331]
prime = list()

cnt = 0
for i in range(331, 100004):
  for j in num:
    if i%j == 0:
      cnt = 1
  if cnt == 0:
    prime.append(i)
  cnt = 0

primes = num + prime

x = int(input())

if x in primes:
  print(x)
else:
  if x%2 == 0:
    x -= 1
  while x > 0:
    x += 2
    if x in primes:
      print(x)
      break

Submission status: Accepted

Solution code:
prime_table = [True]*(2*(10**5)+1)
prime_table[0], prime_table[1] = False, False
i = 2
while i * i <= 2*(10**5):
  if prime_table[i]:
    j = i*i
    while j <= 2*(10**5):
      prime_table[j] = False
      j += i
  i += 1
x = int(input())
ans = x
while not prime_table[ans]:
  ans += 1
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())
j = 0
while is_prime(x+j)==False:
  j += 1
print(x+j)

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]]

lst = primes(100003)
X=int(input())
for i in lst:
    if i>=X:
        print(i)
        exit()

Submission status: Accepted

Solution code:
import math
X = int(input())
if X == 2:
    print(2)
    exit()
X = X-1
while X:
    X += 1
    for j in range(2,int(math.sqrt(X))+1):
        if X%j == 0:
            break
        elif j == int(math.sqrt(X)) and X%j != 0:
            print(X)
            exit()

Submission status: Accepted

Solution code:
x = int(input())

serach_number = x

def sieve_of_eratosthenes(target):
    dest = int(target**(0.5))
    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)
 
 
        i = 0
 
        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1

    return prime_list
prime_list = sieve_of_eratosthenes(serach_number)

if x in prime_list:
    print(x)
else:
    ans = x

    hantei = False
    while not(hantei):
        ans = ans + 1
        hantei = True
        for i in prime_list:
            if ans % i == 0: #全部割り切れなかったらTrue(素数)
                hantei = False
    print(ans)

Submission status: Accepted

Solution code:
li = []

def is_prime(n):
  for m in li:
    if m * m > n: 
      return True
    if n % m == 0:
      return False
  return True

n = int(input())
for i in range(2, n):
  if is_prime(i):
    li.append(i)

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