THIEUNHI203 - PT TỔNG 2 SỐ NGUYÊN TỐ

Điểm: 0,10 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

Tuyển chọn các bài code thiếu nhi v24

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Phân tích số n thành tổng của 2 số nguyên tố. Nếu có nhiều cách phân tích, chọn cách phân tích thành tổng 2 số nguyên tố gần nhau nhất. n ≤ 10^7

Ví dụ:

INPUT

OUTPUT

7 11

Nguồn sách

Bình luận

Hãy đọc nội quy trước khi bình luận.

NguyenAnPhu2013 đã bình luận lúc 5, Tháng 12, 2024, 14:37

mã py của tớ các bạn tham khảo nhé:

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return is_prime

def find_closest_prime_sum(n):
    is_prime = sieve_of_eratosthenes(n)

    closest_pair = None
    min_difference = float('inf')

    for p1 in range(2, n // 2 + 1):
        if is_prime[p1] and is_prime[n - p1]:
            p2 = n - p1
            if abs(p1 - p2) < min_difference:
                closest_pair = (p1, p2)
                min_difference = abs(p1 - p2)

    return closest_pair
n = int(input())
result = find_closest_prime_sum(n)
print(result[0],result[1])