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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

X = int(input())

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

while 1:
    if is_prime(X) == False:
        X = X+1
        continue
    else:
        print(X)
        break

Submission status: Accepted

Solution code:
X = int(input())

def isPrime(n):
  if n < 2:
    return False
  i = 2
  while i*i <= n:
    if n%i == 0:
      return False
    i += 1
  return True

for i in range(X,X+10**5):
    if isPrime(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
import sys
from math import sqrt
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

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

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]]
a=primes(110000)
n=int(input())
for i in range(10000):
    if n+i in a:
        print(n+i)
        break

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
x=int(input())
import fractions
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
while True:
  d=list((prime_decomposition(x)))
  if len(d)==1:
      break
  x+=1
print(x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


@mt
def slv(X):
    P = eratosthenes(10**6)
    return P[bisect.bisect_left(P, X)]


def main():
    X = read_int()
    print(slv(X))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def main():

    X = int(input())
    if X == 1: return 2

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

    n = X
    while True:
        if isprime(n):
            return n
        n += 1
    return -1

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

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

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

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    x=int(input())
    sosu=0
    i=x
    while True:
        if sosuhante(i):
            sosu=i
            break
        i+=1
    print(sosu)












if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import array


def sieve_of_eratosthenes(end, typecode="L"):
    assert end > 1
    is_prime = array.array("B", (True for i in range(end)))
    is_prime[0] = False
    is_prime[1] = False
    primes = array.array(typecode)
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


def solve(x):
    primes = sieve_of_eratosthenes(x * 5)
    for p in primes:
        if x <= p:
            return p


def main():
    x = int(input())
    p = solve(x)
    print(p)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
#    ret = []
    for i in range(N+1):
        if work[i]:
#            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return work

def main():
    primes = eratosthenes(2*10**5)
    X = int( input())
    for i in range(X, 2*10**5):
        if primes[i]:
            print(i)
            return
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	N = INT()
	primes = get_sieve_of_eratosthenes(10**5+100)
	for p in primes:
		if p>=N:
			print(p)
			sys.exit()

if __name__ == '__main__':
	main()

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

Submission status: Accepted

Solution code:
X=int(input())
n=100005
prime = [True for i in range(n + 1)] 
p = 2
while (p * p <= n): 
    if (prime[p] == True): 
        for i in range(p * 2, n + 1, p): 
            prime[i] = False
    p += 1
prime[0]= False
prime[1]= False
for p in range(X,n+1): 
    if prime[p]: 
        print(p)
        break

Submission status: Accepted

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

    x = int(input())

    if x <= 2:
        print(2)
        return

    if x % 2 == 0:
        x += 1

    while not is_prime(x):
        x += 2

    print(x)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
x = int(input())

import math


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

data = get_sieve_of_eratosthenes(10 ** 5 + 3)

for d in data:
    if d >= x:
        print(d)
        break

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())
for i in range(X,10**6):
    if isPrime(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
def is_prime(n):
    flag = True
    for i in range(2, int(n**0.5)):
        if n%i == 0:
            flag = False
            break
    return flag

X = int(input())

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

Submission status: Accepted

Solution code:
x= int(input())
y = x + 10**4
A = [0] * y
i = 2
while i < y:
    while i<y and A[i] == 1:
        i += 1
    j = i*2
    while j < y:
        A[j] = 1
        j += i
    i += 1
ans = x
# print(A[:100])
while A[x] > 0:
    x += 1
print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(X: int):
    def eratos(n :int):
        isPrimeList = [True] * (n+1)
        isPrimeList[0] = isPrimeList[1] = False
        
        for i in range(2, int(n**0.5+1)):
            if(isPrimeList[i]):
                j = i+i
                while(j <= n):
                    isPrimeList[j] = False
                    j = j+i
                    
        return isPrimeList

    t = eratos(10**6)
    # print(t[:10])
    l = [i for i,v in enumerate(t) if t[i] == True] 
    
    for i in l:
        if i >= X:
            print(i)
            exit()
            
    

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

X = int(input())
inf = 10 ** 5 + 10


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


prime_list = primes(inf)

for p in prime_list:
    if p >= X:
        print(p)
        exit()

Submission status: Accepted

Solution code:
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    x = int(input())
    while True:
        if is_prime(x):
            print(x)
            return
        else:
            x += 1
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
table=[1 for i in range(10**5+10)]

table[0]=0
table[1]=0
for i in range(int(len(table)**0.5)+10):
    if table[i]==0:
        continue

    k=2
    while True:
        try:
            table[k*i]=0
            k+=1
        except IndexError:
            break

X=int(input())

while table[X]==0:
    X+=1
print(X)

Submission status: Accepted

Solution code:
import math
import bisect
# 0以上整数x「未満」の素数をリストに格納して返す


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]


prime = primes(10**5+10)
X = int(input())
print(prime[bisect.bisect_left(prime, 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


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

Submission status: Accepted

Solution code:
# coding: utf-8
from bisect import bisect_left
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())
L = primes(10**6)
idx = bisect_left(L, X)
print(L[idx])

Submission status: Accepted

Solution code:
n = int(input())
da = [True for i in range(n + 1000)]
da[0] = False
da[1] = False
now = 2
while now < len(da):
    jj = now * 2
    while jj < len(da):
        da[jj] = False
        jj += now
    now += 1
now = n
while 1:
    if da[now]:
        print(now)
        break
    now+=1