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:
import math

r = int(input())


def is_prime2(q,k=100):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    for i in range(3,k):
        x,y = q,i
        while y:
            x, y =  y, x % y
        if x != 1: continue
        if pow(i, q-1, q) != 1:
            return False
    return True


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

while True:
    if is_prime2(r):
        break
    r += 2

print(r)

Submission status: Wrong Answer

Solution code:
x =  int(input())

def primes(z, n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(z, 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 = primes(x, 10**5)
ans = Prime[0]
print(ans)

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

n=int(input())
for i in range(n,10**6):
    if is_prime(i) is True:
        print(i)
        exit()

Submission status: Wrong Answer

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

num = int(input())

for i in range(num,100001):
  if isPrime(i):
    print(i)
    break

Submission status: Wrong Answer

Solution code:
import sys
x=int(input())
if x==2:
  print(2)
  sys.exit()
for i in range(x,10**5+1):
  for j in range(2,round(i**0.5)+1):
    if i%j==0:
      break
    if j==round(i**0.5) and i%j!=0:
      print(i)
      sys.exit()

Submission status: Wrong Answer

Solution code:
import math
 
number = int(input())
 
def trial_division(target):
    dest = int(math.sqrt(target))
 
    for i in range(2,dest):
        if target % i == 0:
            return False
    return True

for i in range(10000):
    if trial_division(number):
        print(number)
        break
    else:
        number += i

Submission status: Wrong Answer

Solution code:
# C
X = int(input())

# 一覧を求める
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

l = seachPrimeNum(10**5+3)


for i in l:
    if i > X:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())

if n < 3:
    print(3)
    sys.exit(0)
elif n < 5:
    print(5)
    sys.exit(0)
elif n < 7:
    print(7)
    sys.exit(0)


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

new = n +  (6 - (n % 6))
while True:
    if new - 1 > n:
        if is_prime(new):
            print(new - 1)
            sys.exit(0)
    if is_prime(new + 1):
        print(new + 1)
        sys.exit(0)
    new += 6

Submission status: Wrong Answer

Solution code:
primes = [2]

x = int(input())
for i in range(3, x * 2):
    is_p = True
    for p in primes:
        if i < p * p:
            break
        if i % p == 0:
            is_p = False
            break
    if is_p:
        primes.append(i)

print([i for i in primes if i > x][0])

Submission status: Wrong Answer

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):
  for prime in primes:
    if i % prime == 0:
      break
  else:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
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

if x==2:
    print(2)
elif x%2==0:
    for i in range(1,100,2):
        if is_prime(x+i):
            print(x+i)
            exit()
        else:
            pass
else:
    for i in range(2,100,2):
        if is_prime(x+i):
            print(x+i)
            exit()
        else:
            pass

Submission status: Wrong Answer

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############

X = int(input())

def factorize(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result
while len(factorize(X))>1:
    X+=1
print(X)

Submission status: Wrong Answer

Solution code:
x=int(input())
li=[2,3]
i=3
while li[-1]<x:
    for j in range(len(li)):
        if i%li[j]==0:
            break
        elif j==len(li)-1 and i%li[-1]!=0:
            li.append(i)    
    i+=2
    
print(li[-1])

Submission status: Wrong Answer

Solution code:
"""
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*10000):
	if is_prime(i)==True:
		print(i)
		break

Submission status: Wrong Answer

Solution code:
# coding: utf-8
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

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

Submission status: Wrong Answer

Solution code:
import math

x = int(input())


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

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

i = 0
while True:
    if is_prime(x+i):
        break
    i += 1

print(x+i)

Submission status: Wrong Answer

Solution code:
import math

r = 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


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

while True:
    if is_prime(r):
        break
    r += 2

print(r)

Submission status: Wrong Answer

Solution code:
import math
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

X = int(input())
for i in range(X+1,10**8+1):
    if is_prime(i):
        print(i)
        break

Submission status: Wrong Answer

Solution code:
def main():
    x = int(input())
    sosuu = [2]
    A = 200000
    for L in range(3, A, 2):
        for L2 in sosuu:
            if L % L2 == 0:
                break
        else:
            sosuu.append(L)
            if L >= x:
                print(L)
                break
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import ceil, sqrt
n = int(input())

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

notPrime = True
while notPrime:
    for i in range(2, ceil(sqrt(n))):
        if n % i == 0:
            n += 2
            break
    notPrime = False

print(n)

Submission status: Wrong Answer

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

num = int(input())

for i in range(num+1,10000):
  if isPrime(i):
    print(i)
    break

Submission status: Wrong Answer

Solution code:
n=int(input())
prime_list=[2]
for i in range(3,1000000,2):
    if all(i%prime!=0 for prime in prime_list):
        if i<n:
            prime_list.append(i)
        else:
            print(i)
            exit()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x=int(readline())
def a(n):
  for i in range(2, int(n ** 0.5 + 1)):
    if n % i == 0:
      return False
  return True
  
  
n=x+1
while True:
  if a(n):
    print(n)
    quit()
  n+=1

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

def main():
  X = int(input())

  n = X
  while not is_prime(n):
      n += 1

  print(n)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
X=int(input().rstrip())
maxX=10**5

def resolve():
    check,table=sieve(maxX)

    for a in table:
        if a>=X:
            print(a)
            return

def sieve(n):#n以下の素数を返す, is_prime[i]:iが素数ならtrue、table[i]:小さい順に素数入る
    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]]
    is_prime=[False]+is_prime ##[False]は勝手につけた、累積和をするときはこの影響で[0]+いらない
    return is_prime, table


import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """20"""
        output = """23"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """2"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """99992"""
        output = """100003"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Wrong Answer

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

################ DANGER ################
test = ""
#test = \
"""
20
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
        
n = int(input2())

def primes(n):
    ps = [2]
    for odd in range(3, n + 1, 2):
        for p in ps:
            if odd % p == 0:
                break
            if p ** 2 > odd:
                ps.append(odd)
                break
    return ps


def isprime(n):
    last = int(n**.5)
    for m in primes(last):
        if n % m == 0:
            return False
    return True


i = n
while not isprime(i):
    i += 1
    
print(i)

Submission status: Wrong Answer

Solution code:
A = int(input())
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 sys
import bisect
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

n = int(read())
n *= 2

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)

idx = bisect.bisect_left(primes, n //2)


print(primes[idx])

Submission status: Wrong Answer

Solution code:
n = 100000
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)
x=int(input())
for i in primes:
    if i>=x:
        print(i)
        exit()

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

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

a = int(input())

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

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 is_prime(X) is False:
    X += 1
print(X)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

import math
import collections


def factorial(n):
    # 試し割りによる素因数分解
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def solve(X: int):

    for i in range(X, 2*(10**5)):
        c = factorial(i)
        if len(c) == 1:
            break
    print(i)

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

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

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

while True:
    if is_prime(X):
        break
    X += 2

print(X)

Submission status: Wrong Answer

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

x = int(input())

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

print(x)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

def init_prime(n_max: int):
    """ https://qiita.com/fantm21/items/5e270dce9f4f1d963c1e
    # returns prime list [2..n_max]
    """
    if n_max <= 1: return []
    if n_max == 2: return [2,]
    prime = [2,]
    _app_p = prime.append
    n_rt = int(n_max**.5)
    data = list(range(3, n_max+1, 2))
    while data:
        p = data[0]
        if p > n_rt:
            return prime + data
        _app_p(p)
        data = [e for e in data if e%p]


def main():
    N = int(input())
    vP = init_prime(N+50)
    #print("... " if len(vP)>16 else "", end="")
    #print(*vP[-16:])
    #print("counts: ", len(vP))
    for p in vP:
        if p >= N:
            print(p)
            return


if __name__ == "__main__":
    main()