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: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

X = int(input())

while(True):
    flag = is_prime(X)
    if flag:
        print(X)
        break
    if X%2==0:
        X+=1
    else:
        X+=2

Submission status: Wrong Answer

Solution code:
import math
def isprime(limit):
    for k in range(limit, limit + 100000):
        if k % 2 == 0 and k != 2:
            continue
        for divisor in range(2, math.floor(math.sqrt(k)) + 1):
            if k % divisor == 0:
                break
            if divisor == math.floor(math.sqrt(k)):
                return k
num = int(input())
print(isprime(num))

Submission status: Wrong Answer

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())
while True:
  n += 1
  if is_prime(n):
    print(n)
    exit()

Submission status: Wrong Answer

Solution code:
#--import&define---------------------
import math
import sys
input = sys.stdin.readline
def yes():
    print("Yes")
def no():
    print("No")

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
#--以下解答---------------------------------
x = int(input())
prime_list = primes(10**6)

i = x+1
flag = True
while True:
    if prime_list[i] == True:
        print(i)
        sys.exit()
    i += 1

Submission status: Wrong Answer

Solution code:
import math

x = int(input())

tmp = int(math.sqrt(x))

if x == 2:
    print(2)

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

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

    if count == 0:
        print(x)
        break

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

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

Submission status: Wrong Answer

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**5
for i in  range(N,MAX+1):
  if not soinsuu(i):
    print(i)
    break

Submission status: Wrong Answer

Solution code:
x = int(input())


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


def next_prime(n):
    if n <= 1:
        return 2
    prime = n
    found = False
    while not found:
        prime = prime + 1
        if is_prime(prime):
            found = True

    return prime


print(next_prime(x))

Submission status: Wrong Answer

Solution code:
x=int(input())
li=[2,3,5]
p=6
i=0
prime=False
while p<x or prime==False:
    prime=True
    p+=1
    for i in range(len(li)):
        if p%li[i]==0:
            prime=False
    if prime:
        li.append(p)
    
li.sort(reverse=True)
print(li[0])

Submission status: Wrong Answer

Solution code:
import math

prime_numbers=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  m = math.floor(math.sqrt(n))
  for p in prime_numbers:
      if n % p == 0:
        return False
      if p > m:
        break
  return True

x=float(input())
a3=False
if isPrime(x):
    x+=1
while a3 == False:
    a3=isPrime(x)
    x+=1
print(int(x-1))

Submission status: Wrong Answer

Solution code:
X = int(input())

def segment_sieve(a, b, MAX_LEN=10 ** 6 + 7):
    is_prime_small = [True] * MAX_LEN
    is_prime = [True] * MAX_LEN
    
    small_len = int(b ** 0.5) + 1
    for i in range(2, small_len):
        if is_prime_small[i]:
            for j in range(i * 2, small_len, i):
                is_prime_small[j] = False
                
            for j in range(a // i * i, b, i):
                is_prime[j - a] = False
                
    return is_prime

if X == 2:
    print(2)
else:
    for i, flag in enumerate(segment_sieve(X, 100007)):
        if flag:
            print(X + i)
            break

Submission status: Wrong Answer

Solution code:
def if_prime(x):
    for i in range(2,x):
       if (x % i) == 0:
           return False
    return True

x = int(input("Enter x: "))

if x <= 1 or x > 10 ** 5:
    print("Input not follow the constraint")
else:
    x = x + 1
    while not if_prime(x):
        x = x + 1
    print(x)

Submission status: Wrong Answer

Solution code:
import math

prime_numbers=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  m = math.floor(math.sqrt(n))
  for p in prime_numbers:
      if n % p == 0:
        return False
      if p > m:
        break
  return True

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

Submission status: Wrong Answer

Solution code:
import math 

def isPrime(n): 

    if(n <= 1): 
        return False
    if(n <= 3): 
        return True
    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
def nextPrime(N): 
    if (N <= 1): 
        return 2
    prime = N 
    found = False 
    while(not found): 
        prime = prime + 1
        if(isPrime(prime) == True): 
            found = True
    return prime 
N = int(input())
print(nextPrime(N))

Submission status: Wrong Answer

Solution code:
X=int(input())
n=10**5+1
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)
for i in range(X,n):
  if i in primes:
    print(i)
    break

Submission status: Wrong Answer

Solution code:

MAX_SIZE = int(1e6)

prime = [True] * (MAX_SIZE + 1)

def seive():
    p = 2

    while (p * p <= MAX_SIZE):
        if (prime[p] == True):

            for i in range(p * p, MAX_SIZE, p):
                prime[i] = False
        p += 1
def PrimeFinder(n, k):
    res = -1
    for i in range(n + 1, MAX_SIZE):
        if (prime[i] == True):
            k -= 1
        if (k == 0):
            res = i
            break

    return res
if __name__ == '__main__':
    n = int(input())
    seive()
    print(PrimeFinder(n, 1))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
"""
n,k = (int(_) for _ in input().split())
R,S,P = (int(_) for _ in input().split())
t = list(input())
a ={"r":P,"s":R,"p":S}
Q = n//k
q = n%k
ans = 0
for i in range(k):
	ans+=a[t[i]]
ans = ans*Q
for i in range(n-q,n-1):
	ans+=a[t[i]]

for i in range(k,):
	if t[i]==t[i-k]:
		ans-=a[t[i]]
"""

"""
n,k = (int(_) for _ in input().split())
r,s,p = (int(_) for _ in input().split())
t = input()]
"""

def is_prime(q):
    q = abs(q)
    if q == 2:
    	return True
    if q < 2 == 0:
    	return False
    return pow(2, q-1, q) == 1

x = int(input())
for i in range(x,100004):
	if is_prime(i)==True:
		print(i)
		break

Submission status: Wrong Answer

Solution code:
#C - Next Prime
X=int(input())

def is_prime(q):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

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

print(q)

Submission status: Wrong Answer

Solution code:
def check(num):
    if num > 1:
        for i in range(2, num):
            if (num % i) == 0:
                return False
                break
        else:
            return True
    else:
        return False


a = int(input())

while a > 0:
    a += 1
    if check(a):
        print(a)
        break

Submission status: Wrong Answer

Solution code:
a = int(input())

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > a]

s = (sieve(a * 2))
print(s[0])

Submission status: Wrong Answer

Solution code:
X = int(input())


def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1


def solve(X):
    judge = False
    while not judge:
        if (is_prime(X)):
            return X
        X += 1


print(solve(X))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

    primes = [2,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 == 0:
                isPrime = False
                break
        if isPrime:
            return x
        else:
            x += 2

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

Submission status: Wrong Answer

Solution code:
import numpy as np
def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
n=int(input())
pri1=seachPrimeNum(n)
ma=pri1.index(max(pri1))
pri=seachPrimeNum(n*2)
print(pri[ma+1])

Submission status: Wrong Answer

Solution code:
pn=[2]
k = int(input())
import sys
A=10000
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)
for r in pn:
  if k<r:
    print(str(r))
    sys.exit()

Submission status: Wrong Answer

Solution code:
x = int(input())
while(1):
  flag=0
  for i in range(int(x/2)):
    if x%(i+2)==0:
      flag=1
  if flag==0:
    print(x)
    exit()
  x+=1

Submission status: Wrong Answer

Solution code:
"""
n,k = (int(_) for _ in input().split())
R,S,P = (int(_) for _ in input().split())
t = list(input())
a ={"r":P,"s":R,"p":S}
Q = n//k
q = n%k
ans = 0
for i in range(k):
	ans+=a[t[i]]
ans = ans*Q
for i in range(n-q,n-1):
	ans+=a[t[i]]

for i in range(k,):
	if t[i]==t[i-k]:
		ans-=a[t[i]]
"""

"""
n,k = (int(_) for _ in input().split())
r,s,p = (int(_) for _ in input().split())
t = input()]
"""

def is_prime(q):
    q = abs(q)
    if q == 2:
    	return True
    if q < 2 or q&1 == 0:
    	return False
    return pow(2, q-1, q) == 1

x = int(input())
for i in range(x,x*1000000000000000000000):
	if is_prime(i)==True:
		print(i)
		break

Submission status: Wrong Answer

Solution code:
num, found = int(input()), False
def checkPrime(n):
    for x in (2, n):
        if n%x == 0:
            return False
            break
        else: return True
while not found:
    num += 1
    if checkPrime(num):
        found = True
        print(num)

Submission status: Wrong Answer

Solution code:
n = int(input())

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


while True:

    for i in range(3, n):
        if n % i == 0:
            n += 2
            continue

    break

print(n)

Submission status: Wrong Answer

Solution code:
import math
x = int(input())
def check(x):
    for i in range(2, int(math.sqrt(x) + 1)):
        if x % i == 0:
            return False
    return True

for i in range(x, 100000):
    if check(i) == True:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
X = int(input())

for i in range(1, 10**5 - X):
    for j in range(2, X):
        if X % j == 0:
            X = X + i

print(X)

Submission status: Wrong Answer

Solution code:
n= int(input())

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
def fun(n):
    i = n+1
    while 1:
        if isprime(i):
            break
        i+=1
    return i

print(fun(n))

Submission status: Wrong Answer

Solution code:
import math

prime_numbers=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  m = math.floor(math.sqrt(n))
  for p in prime_numbers:
      if n % p == 0:
        return False
      if p > m:
        # 素数がnの平方根を超えたら終了
        break
  return True

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

Submission status: Wrong Answer

Solution code:
x = int(input())


def is_prime(n):
    if n < 2: return False
    for x in range(2, int(n ** 0.5) + 1):
        if n % x == 0:
            return False
    return True


def next_prime(n):
    if n <= 1:
        return 2
    prime = n
    found = False
    while not found:
        prime = prime + 1
        if is_prime(prime):
            found = True

    return prime


print(next_prime(x))

Submission status: Wrong Answer

Solution code:
def isPrime(n):
    for i in range(2,N):
        if N%i == 0:
            return False
    
def find_next_prime(n):
    return find_prime_in_range(n, 2*n)

def find_prime_in_range(a, b):
    for p in range(a, b):
        for i in range(2, p):
            if p % i == 0:
                break
        else:
            return p
    return None

N = int(input())
if(isPrime(N)):
    print(str(N))
else:
    print(str(find_next_prime(N+1)))

Submission status: Wrong Answer

Solution code:
x = int(input())
n = 100000
primes = set(range(3, n+1, 2))|set([2])
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*3, n+1, i*2))
primes=list(primes)
for i in primes:
  if i >=x:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
X = int(input())

prime_numbers = [2, 3,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

import math

def isPrime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    m = math.floor(math.sqrt(n))
    for p in prime_numbers:
        if n % p == 0:
            return False
        if p > m:
            # 素数がnの平方根を超えたら終了
            break
    return True
  
while True:
    if isPrime(X):
        print(X)
        break
    else:
        X += 1

Submission status: Wrong Answer

Solution code:
import numpy as np

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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())
prime = np.array(primes(200000))
idx = np.array(np.where(prime > X))
idx = idx[0]
ans = prime[idx[0]]
print(ans)

Submission status: Wrong Answer

Solution code:
A = int(input())
if A == 2:
    print(2)
sosu = [2] #素数が入る
sosu_2 = [4] #素数の2乗の数が入る
sosu_2_index = 1
for num in range(3, 100010, 2):
    if  num > sosu_2[sosu_2_index-1]:
        sosu_2_index += 1
    flag =  True
    for i in range(1,sosu_2_index):
        if num % sosu[i] == 0:
            flag = False
            break
    if flag:
        sosu.append(num)
        if num >= A:
            print(num)
            exit()
        sosu_2.append(num**2)

Submission status: Wrong Answer

Solution code:
import math

prime_numbers=[3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  m = math.floor(math.sqrt(n))
  for p in prime_numbers:
      if n % p == 0:
        return False
      if p > m:
        # 素数がnの平方根を超えたら終了
        break
  return True

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
x = int(input())

def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    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:
        for i in range(x+1, 10**5+100, 2):
            if is_prime(i):
                return i

print(func(x))

Submission status: Wrong Answer

Solution code:
x = int(input())
m = [2,3,5]
z = [0]*x
y = 0

for i in range(7,321):
    c = 0
    for j in range(i):
        if i%(j+1) == 0:
            c += 1
    if c == 2:
        m.append(i)
        
for i in range(x):
    z[i] = i+1

if x>332:  
    for i in range(x):
        for j in range(len(m)):
            if (i+1) % m[j] == 0:
                z[i] = 0
         
    print(max(z))

else:
    for i in range(len(m)):
        if x >= m[i]:
            y = m[i]
    print(y)

Submission status: Wrong Answer

Solution code:
X = int(input())

def segment_sieve(a, MAX_LEN=10**6+7):
    is_prime_small = [True] * MAX_LEN    
    is_prime = [True] * MAX_LEN
    
    small_len = a + 1
    for i in range(2, small_len):
        if is_prime_small[i]:
            for j in range(i * 2, small_len, i):
                is_prime_small[j] = False
                
            for j in range(a // i * i, a * 2, i):
                is_prime[j - a] = False
                
    return is_prime

if X == 2:
    print(2)
else:
    for i, flag in enumerate(segment_sieve(X)):
        if flag:
            print(X + i)
            break

Submission status: Wrong Answer

Solution code:
x = int(input())
if (x >= 2):
    print(2)
    exit()
prime_list = [2]
for num in range(3,10**5,2):
    if all(num % prime != 0 for prime in prime_list):
        prime_list.append(num)
        if (num >= x):
            print(num)
            exit()

Submission status: Wrong Answer

Solution code:
def check(num):
    if num > 1:
        for i in range(2, num):
            if (num % i) == 0:
                return False
                break
        else:
            return True
    else:
        return False


a = int(input())

for i in range(a, 100000):
    if check(i):
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import math
x = int(input())
def check(x):
    for i in range(2, int(math.sqrt(x) + 1)):
        if x % i == 0:
            return False
    return True

for i in range(x, 10000):
    if check(i) == True:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
n = int(input())
m=0
primeN=[prime for prime in range(2, n) if prime not in [notAPrime for i in range(2, int(n**0.5)) for notAPrime in range(i * 2, n, i)]]
for d in range(n,9*n):
    if m==1:
        break
    for t in primeN:
        if d%t==0:
            break
        if t==primeN[-1]:
            print(d)
            m=1
            break

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    if q == 2: return True
    elif q % 2 == 0: return False
    return pow(2, q-1, q) == 1

a = int(input())

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

Submission status: Wrong Answer

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def sosu(x):
    arr = factorization(x)
    if len(arr) == 1:
        return True
    else:
        return False

def solve(X: int):
    ans = 100003
    for i in range(X, 10**5 + 1):
        if i % 2 == 0 and X != 2:
            continue
        if sosu(i):
            ans = i
            break

    print(ans)

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