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 math

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


# 整数xが素数かどうかを判定する
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


if __name__ == '__main__':
    x = int(input())
    
    while(not is_prime(x)):
        x += 1
        
    print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n=int(input())
if n % 2 == 0 and n != 2:
        n += 1
while n <= n + 20:
    i=3
    while i <= math.sqrt(n):
        if n % i == 0:
            break
        else:
            i += 2
    if i >= math.sqrt(n):
        print(n)
        break
    else:
        n+=2

Submission status: Accepted

Solution code:
# Python 3 program to print the Kth 
# prime greater than N 

# set the MAX_SIZE of the array to 10^6 
MAX_SIZE = int(1e6) 

# initialize the prime array 
prime = [True] * (MAX_SIZE + 1) 

# Code for Sieve of Eratosthenes 
def seive(): 
	p = 2
	
	while (p * p <= MAX_SIZE): 
		
		# if prime[p] is not changed, 
		# then it is a prime 
		if (prime[p] == True): 
			
			# update all multiples of p 
			for i in range(p * p, MAX_SIZE, p): 
				prime[i] = False
		p += 1

# Function to find the kth prime 
# greater than n 
def kthPrimeGreaterThanN(n, k): 
	res = -1
	
	# looping through the numbers 
	# greater than n 
	for i in range(n, MAX_SIZE): 
		
		# decrement k if i is prime 
		if (prime[i] == True): 
			k -= 1
		
		# store the kth prime greater than n 
		if (k == 0): 
			res = i 
			break
	
	return res 

# Driver Code 
n = int(input())
k = 1
seive() 
print(kthPrimeGreaterThanN(n, k)) 	
# This code is contributed by Rupesh Rao

Submission status: Accepted

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

while 'true':
    tmp = int(numpy.sqrt(X)) + 1
    for i in range(2, tmp + 1):
        if X % i == 0 and X != 2:
            break
        elif i == tmp:
            print(X)
            sys.exit(0)
    X += 1

Submission status: Accepted

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

count=1

if X==2:
    count=0

while(count==1):
    for n in range(2,X):
        if (X%n==0):
            X+=1
            break
        if (n>math.sqrt(X)):
            count=0
            break
print(X)

Submission status: Accepted

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

def checkp(X):
    p=3
    pmax=X**0.5
    while X%p!=0:
        p+=2
        if p>pmax:
            return True
    return False

def solve(X: int):
    if X==2:
        print(2)
        return
    if X%2==0:
        X+=1
    while not checkp(X):
        X+=2
    print(X)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import sys
input = sys.stdin.readline
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]]
def print_ans(X):
    """Test Case
    >>> print_ans(20)
    23
    >>> print_ans(2)
    2
    >>> print_ans(99992)
    100003
    """
    ord = 10 ** 6
    prime_list = primes(ord)
    for i in prime_list:
        if i >= X:
            print(i)
            break
if __name__ == '__main__':
    # test
    X = int(input().rstrip())
    print_ans(X)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
so=0
if n==2:
  print(2)
  so=1
elif n!=2 and n%2==0:
  n+=1
for j in range(n,n+2000,2):
  divisors = []
  for i in range(1, int(j**0.5)+1):
      if j % i == 0:
          divisors.append(i)
          if i != j // i:
              divisors.append(j//i)
  x=divisors
  t=len(x)
  if t==2 and so==0:
    print(x[1])
    break

Submission status: Accepted

Solution code:
x = int(input())
n = 2 *(10 ** 5)
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes = list(primes)
import bisect
b = bisect.bisect_right(primes, x)
if x == primes[b - 1]:
    print(x)
else:
    print(primes[b])

Submission status: Accepted

Solution code:
def check(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True


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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
x=int(input())
if x==2 or x==3:
    print(x)
    exit()
for i in range(x,10**6):
    if i%2==0:
        continue
    cnt=0    
    for j in range(3,x,2):
        if i%j==0:
            cnt+=1
            break
    if cnt==0:
        print(i)
        exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def primes(n):
    """ 
    Input n>=6, Returns a list of primes, 2 <= p < n 
    6以上の数であれば p (素数) <= n のlistを返す 
    :param int n:
    :rytpe list:
    """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

#solve
def solve():
    x = II()
    p = primes(10 ** 6)
    print(p[bisect_left(p, x)])
    return


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

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:
            return False
    return True

if __name__ == "__main__":
    X = input()
    X = int(X)
    while(True):
        flg = trial_division(X)
        if flg:
            print(X)
            exit(0)
        else:
            X += 1
    print(X)

Submission status: Accepted

Solution code:
import math
X = int(input())
for i in range(X,10**6):
    flag = True
    for j in range(2,int(i**0.5+1)):
        if (i%j) == 0:
            flag = False
            
            break
    if flag:
        print(i)
        exit()

Submission status: Accepted

Solution code:
X = int(input())
prime = None
while True:
    for i in range(2, X):
        if X % i == 0:
            break
    else:
        prime = X
    if prime != None:
        break
    else:
        X += 1

print(prime)