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:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000001
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
sieve()
x = int(input())
for i in range(x,MAXN):
    if spf[i]==i:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys

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

import math

def Judge_PrimeNum(n):
    t = []
    d = math.ceil(n**(1/2))
    for i in range(2,d+1):
        if n%i == 0:
            t.append(i)
            
    if len(t) == 0:
        return -1
    else:
        return t

while True:
	ans = Judge_PrimeNum(x)
	if ans == -1:
		ans = x
		break
	else:
		x += 1
		continue

print(ans)

Submission status: Accepted

Solution code:
def sieve():
    n = 100003
    prime_list = []
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        f = is_prime[i]
        if f:
            prime_list.append(i)
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i

    return prime_list

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

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

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

Submission status: Accepted

Solution code:
x = int(input())

def sieve(lim):
    primes = [True] * (lim+1)
    primes[0:2] = False, False
    for i in range(2, int(lim**0.5)+1):
        if not primes[i]: continue
        for j in range(i*2, lim+1, i):
            primes[j] = False
    return primes

p = sieve(10**6)

for i in range(x, 10**6):
    if p[i]: print(i); exit()

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def eratosthenes_sieve(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

X = INT()

primes = sorted(eratosthenes_sieve(2 * 10**5))

for prime in primes:
    if prime >= X:
        print(prime)
        exit()

Submission status: Accepted

Solution code:
X = int(input())
def eratosthenes(N):
  s = [i % 2 for i in range(N)]
  s[0] = s[1] = 0
  s[2] = 1

  for i in range(2, int(N**0.5)):
    if s[i] == 0: continue
    for j in range(2 * i, N, i):
      s[j] = 0
  
  return s

s = eratosthenes(10**5 + 10)
for i in range(X, 10**5+10):
  if s[i] == 1:
    print(i)
    break

Submission status: Accepted

Solution code:
def get_primes(n: int) -> list:
    sieve=[1]*n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i] = [0] * ((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

X=int(input())
D=10**5+4
L=get_primes(D)
import bisect

print(L[bisect.bisect_left(L,X)])

Submission status: Accepted

Solution code:
x = int(input())

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

for i in range(x,10**9):
    if is_prime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
X = int(input())

#nの素数判定
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

for i in range(X,X+1000000):
  if(is_prime(i) == True): 
    ans = i
    break
print(ans)

Submission status: Accepted

Solution code:
X = int(input())

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

while not is_prime(X):
    X += 1

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

Submission status: Accepted

Solution code:
# N以下の素数のリストを出力する
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 f(n):
    import math
    ans = True
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ans = False
    return ans

for i in range(x, 10**9):
    if f(i):
        print(i)
        break

Submission status: Accepted

Solution code:
X = int(input())



for i in range(X, 150000):
        flag = True
        for j in range(2, int(i ** (1/2)) + 1):
                if i % j == 0:
                        flag = False
                        break
        if flag:
                print(i)
                exit()

Submission status: Accepted

Solution code:
N = int(input())

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

for i in range(N,N+10**5):
    if(is_prime(i)):
        print(i)
        exit()

Submission status: Accepted

Solution code:
x = int(input())

def prime(c):
    import math
    if c == 1:
        return False
    for i in range(2, round(math.sqrt(c)) + 1):
        if c % i == 0:
            return False
        else:
            continue
    return True

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

Submission status: Accepted

Solution code:
x = int(input())

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

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, 99999999999999999999999):
  if is_prime(i):
    if i >= n:
      print(i)
      exit()

Submission status: Accepted

Solution code:
x = int(input())
def primes(n):
    #2~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]]

y = primes(10**5*2)

from bisect import bisect_left
print(y[bisect_left(y,x)])

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)
        exit()
    X += 1