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

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


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

Submission status: Accepted

Solution code:
n = int(input())


def prime(n):
    if n == 1:
        n += 1
    while True:
        flag = 0
        for k in range(2, int(n**0.5) + 1):
            if n % k == 0:
                flag = 1
                break
        if flag == 0:
            return n
        n += 1


ans = prime(n)
print(ans)

Submission status: Accepted

Solution code:
import math

target = int(input())

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]

primes = get_sieve_of_eratosthenes(100003)

primes = [s for s in primes if s >= target]

print(min(primes))

Submission status: Accepted

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 and list(c.values())[0] == 1:
            print(i)
            break
    else:
        raise Error

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

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 = int(input())
list = primes(10**5 + 4)
for i in list:
  if i < X:
    continue
  else:
    print(i)
    break

Submission status: Accepted

Solution code:
import math

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

    return True
    

N = int(input())
A = N
while(1):
	B = sosuu(A)
	if B == False:
		A +=1
	elif B == True:
		print(A)
		break

Submission status: Accepted

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

n = int(input())

for i in range(0,10**5):
  if is_prime(n+i)==True:
    print(n+i)
    exit()

Submission status: Accepted

Solution code:
S = int(input())
check = 0

if S == 2 or S == 3:
    print(S)
else:
    while check == 0:
        for i in range(2, int(S ** (1/2))+1):
            if S % i == 0:
                S = S + 1
                break
            elif S % i != 0 and i == int(S ** (1/2)):
                print(S)
                check = 1
                break

Submission status: Accepted

Solution code:
import sys
import math
def is_prime(num):
    if num < 2:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        for prime in range(2, num_sqrt + 1):
            if num % prime == 0:
                return False
                break
        return True

def main():
    x = int(input())
    i = x
    while True:
        if is_prime(i) == True:
            print(i)
            sys.exit()
        i = i + 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
X = int(input())

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

k = 0
for j in range(X,100005):
    a = factorization(j)
    if len(a) == 1 and a[0][1] == 1:
        k = j
        break

print(k)

Submission status: Accepted

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_ = 5*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)

idx = bisect.bisect_left(primes, n)



print(primes[idx])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
X=int(input())
X=X-1
a=0
b=1
while b==1:
    X=X+1
    a=0
    for i in range(2,X):
        if X%i==0:
            a=a+1
    if a==0:
        print(X)
        break;

Submission status: Accepted

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

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: Accepted

Solution code:
n=int(input())
def next(n):    return prime(n, 2*n)
def prime(a, b):
    for p in range(a, b):
        for i in range(2, p):
            if p % i == 0:  break
        else:   return p
    return
print(next(n))