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())
import numpy as np

def seachPrimeNum(N):
    m = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= m:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

s = set(seachPrimeNum(2*x))
for i in range(x):
  if x+i in s:
    u = x+i
    break
print(u)

Submission status: Accepted

Solution code:
from math import sqrt

x = int(input())
n = int(sqrt(x))

prime = False

while not prime:
    for i in range(2, n):
        if x % i == 0:
            x += 1
            break
    else:
        prime = True


print(x)

Submission status: Accepted

Solution code:
X = int(input())
import math 
  
# Function that returns True if n  
# is prime else returns False  
def isPrime(n): 
      
    # Corner cases  
    if(n <= 1): 
        return False
    if(n <= 3): 
        return True
      
    # This is checked so that we can skip  
    # middle five numbers in below loop  
    if(n % 2 == 0 or n % 3 == 0): 
        return False
      
    for i in range(5,int(math.sqrt(n) + 1), 6):  
        if(n % i == 0 or n % (i + 2) == 0): 
            return False
      
    return True
  
if isPrime(X):
    print(X)
    exit()
# Function to return the smallest  
# prime number greater than N  
def nextPrime(N): 
  
    # Base case  
    if (N <= 1): 
        return 2
  
    prime = N 
    found = False
  
    # Loop continuously until isPrime returns  
    # True for a number greater than n  
    while(not found): 
        prime = prime + 1
  
        if(isPrime(prime) == True): 
            found = True
  
    return prime 

print(nextPrime(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 

    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]

def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False

    
    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__':
    target = int(input())
    ps = primes(2 * 10**5)
    ans_idx = bisect.bisect_left(ps, target)
    print(ps[ans_idx])

Submission status: Accepted

Solution code:
X = int(input())
i = 0
end_flag = 1
if X < 4:
    print(X)
else:
    while end_flag == 1:
        ii = 2
        while ii <= (X + i) // 2:
            if (X + i) % ii == 0:
                i = i + 1
                break
            elif ii == X // 2:
                print(X + i)
                end_flag = 0
                break
            ii = ii + 1

Submission status: Accepted

Solution code:
def main():
    x = int(input())

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

    if x == 2:
        return 2
    x += (x+1)%2
    while True:
        isPrime = True
        for p in primes:
            if x == p:
                return p
            if x % p == 0:
                isPrime = False
                break
        if isPrime:
            return x
        else:
            x += 2

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

Submission status: Accepted

Solution code:
N=int(input())
def soinsuu(n):
  t=n//2
  for i in range(2,t):
    if n%i==0:
      return True
  return False
MAX=10**10
for i in  range(N,MAX+1):
  if not soinsuu(i):
    print(i)
    break

Submission status: Accepted

Solution code:
import math

x = int(input())
x -= 1
while(1):
    flag = True
    x += 1
    if x%2 == 0 and x != 2:
        continue
    
    for div in range(2, math.floor(math.sqrt(x))+1):
        if x%div == 0:
            flag = False
            break
    
    if flag:
        print(x)
        break

Submission status: Accepted

Solution code:
import math
x = input()
x = int(x)
if x in [2,3,5,7]:
    print(x)
elif x == 4:
    print(5)
elif x==6:
    print(7)
elif x==8:
    print(11)
else:
    while 1:
        flag = 0
        if x%2==0:
            x= x+1
            continue
        y = 3
        while y<math.sqrt(x):
            if x%y==0:
                break
            y=y+2
            if y>math.sqrt(x):
                flag=1
                break
        if flag == 1:
            print(x)
            break
        x = x+2

Submission status: Accepted

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

def isPrime(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return 0
    return 1

for i in range(a, 100004):
    if isPrime(i):
        print(i)
        break

Submission status: Accepted

Solution code:
x = int(input())

def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  if n % 2 == 0:
    # ２ではない偶数は素数ではない
    return False
  for p in range(3, n, 2): # 奇数だけ計算する
      if n % p == 0:
        return False
  return True

def main(x):
    res = isPrime(x)
    if res == True:
        print(x)
        return

    if res == False:
        main(x+1)

main(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
X = int(input())
ans=0
if (X==2):
    ans=2
if(X==3):
    ans=3

if X % 2 == 0:
    X=X+1
while(1):
    l = math.floor(math.sqrt(X))
    for i in range(2,l+1):
        if (X % i == 0):
            break
        if (i==l):
            #print("A")
            ans = X
    if(ans != 0):
        break
    X = X + 2

print(ans)

Submission status: Accepted

Solution code:
import numpy

def is_prime(n):
    if n == 1: return False

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

    return True

x = int(input())

while(1):
    if is_prime(x) == 1:
        break
    else:
        x = x + 1

print(x)

Submission status: Accepted

Solution code:
x=int(input())
n=x
count_a=0
while(count_a==0):
  div=2
  count=0
  while(div<n):
    if(n%div==0):
      count+=1
    else:
      pass
    div+=1
  if(count==0):
    count_a+=1
  else:
    n+=1
print(n)

Submission status: Accepted

Solution code:
x = int(input())
while True:
    for a in range(2,int(x**0.5)):
        if x%a==0:
            break
    else:
        print(x)
        break
    x += 1

Submission status: Accepted

Solution code:
x = int(input())						# 5


#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


ans = x

while is_prime(ans)==False:
	ans+=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
import math
primes = [2]
for i in range(3, math.ceil(math.sqrt(2*n+1))):
  for prime in primes:
    if i % prime == 0:
      break
  else:
    primes.append(i)
    if i >= n:
      break
for i in range(n, 2*n+1):
  if i in primes:
    print(i)
    break
  else:
    for prime in primes:
      if i % prime == 0:
        break
    else:
      print(i)
      break

Submission status: Accepted

Solution code:
import random

X = int(input())


def is_prime(n):
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True


def solve(X):
    while True:
        if (is_prime(X)):
            return X
        X += 1


print(solve(X))

Submission status: Accepted

Solution code:
import math
X = int(input())
while True:
    i = 2
    if X == 2 or X == 3:
        break
    Y = int(math.sqrt(X))
    while i != Y+1:
        if X % i == 0:
            X += 1
            break
        i += 1
    if i == Y+1:
        break
print(X)

Submission status: Accepted

Solution code:
x = int(input())

def is_prime(x):
    if x % 2 == 0:
        return False

    for i in range(3, x, 2):
        if x % i == 0:
            return False

    return True


def func(x):
    if is_prime(x):
        return x
    else:
        if x % 2 == 0:
            for i in range(x+1, 10**5+100, 2):
                #print(i)
                if is_prime(i):
                    return i

        else:
            for i in range(x, 10**5+100, 2):
                #print(i)
                if is_prime(i):
                    return i




if x == 2:
    print(x)
else:
    print(func(x))

Submission status: Accepted

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

    print(X)

Submission status: Accepted

Solution code:
X = int(input())
a = [True for _ in range((10 ** 5) + 1)]

for i in range(2, int(100000 ** 0.5) + 1):
    j = 2
    while (i * j) <= 100000:
        a[i * j] = False
        j += 1

i = 0
while True:
    if 10 ** 5 < X + i:
        print(100003)
        exit()
    if a[X + i]:
        print(X + i)
        exit()
    i += 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


N = int(input())
MAX = 10 ** 5 + 1
while True:
    if is_prime(N):
        print(N)
        exit()
    else:
        N += 1

Submission status: Accepted

Solution code:
#C - Next Prime
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

q=X
while is_prime(q)==False:
    q=q+1

print(q)

Submission status: Accepted

Solution code:
import numpy as np
def is_prime(N):
    is_prime = True
    for i in range(2, int(np.sqrt(N))):
        if N%i == 0:
            is_prime = False
            break
    return is_prime

X = int(raw_input())
maxx = 100003
for i in range(X, maxx+1):
    if is_prime(i):
        print i
        break

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

i = x
while not is_prime(i):
    i += 1

print(i)

Submission status: Accepted

Solution code:
n = int(input())

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table

_, t = sieve(100003)
t = [i for i in t if i>=n]

print(t[0])

Submission status: Accepted

Solution code:
X = int(input())
for num in range(X, 10000000000):
    if num > 1:
       for i in range(2, num):
           if (num % i) == 0:
               break
       else:
           print(num)
           break

Submission status: Accepted

Solution code:
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

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

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
sosu = 0
n = int(input())
while sosu == 0:
    #print (make_divisors(n))
    if 2 == len(make_divisors(n)):
        sosu = 1
    else:
        n +=1
print (n)

Submission status: Accepted

Solution code:
x = int(input())

def judge_prime(j):
    k = int(j ** 0.5) + 1
    for i in range(2, k):
        if j % i == 0:
            return False # 素数でない
    else:
        return True

j = x
while True:
    if judge_prime(j):
        print(j)
        break
    j += 1