首页 > 试题广场 >

查找组成一个偶数最接近的两个素数

[编程题]查找组成一个偶数最接近的两个素数
  • 热度指数：167430 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的偶数 n，找出两个素数 a,b，满足：
\hspace{23pt}\bullet\,它们的和等于 n；
\hspace{23pt}\bullet\,它们的差值的绝对值最小。

\hspace{15pt}我们可以证明，a,b 一定存在，从小到大输出满足条件的素数对。

输入描述:
\hspace{15pt}输入一个整数 n \left(4 \leqq n \leqq 10^3\right)。保证 n 是偶数。


输出描述:
\hspace{15pt}第一行输出一个整数 a，代表满足条件的素数对中的较小者。
\hspace{15pt}第二行输出一个整数 b，代表满足条件的素数对中的较大者。
示例1

输入

20

输出

7
13
示例2

输入

4

输出

2
2
算法知识视频讲解
添加回答
Python3
序曲已了头像 序曲已了
def check(p):
    for n_ in range(2, int(p ** 0.5) + 1):
        if p % n_ == 0:
            return False
    return True

n = int(input())
a =n // 2
for i in range(0, a - 1):
    if check(a - i) and check(a + i):
        print(a - i)
        print(a + i)
        break
拆分成找素数和差值最小两个问题。其中对于差值最小，题目限制为偶数，则从n/2为起始，迭代寻找出n/2+i和n/2-i皆为素数的第一个i值即可。
发表于 2025-08-01 17:03:43 回复(0)
Python3
土豆耶夫头像 土豆耶夫
nn = input().strip()
n = int(nn)
if n == 4:
    print(2)
    print(2)
else:
    k = int(n / 2)
    for i in range(k, n):
        p = int(i / 2)
        lst1 = []
        for j in range(1, p):
            if i % j == 0:
                lst1.append(j)

        a = i
        if len(lst1) == 1:
            b = n - a
            c = b // 2
            lst2 = []
            for z in range(1, c + 1):
                if b % z == 0:
                    lst2.append(z)
            if len(lst2) == 1:
                print(b)
                print(a)
                break

发表于 2025-06-15 20:50:13 回复(0)
Python3
def__我爱上班__头像 def__我爱上班__ 
n = int(input())
re = [2]
#找素数
for i in range(3,n):
    flag = 0
    for j in range(2,i):
        if i % j == 0:
            flag = 1
            break
    if flag == 0:
        re.append(i)
re.sort()
#双指针判断和
re2 = []
l = 0 
r =len(re)-1
while l <= r:
    if (re[l] + re[r]) == n:
        re2.append((re[l],re[r]))
        l += 1
        r -=1
    elif (re[l] + re[r]) < n:
        l += 1
    else:
        r -= 1
#排序
re2.sort(key= lambda x:x[1]-x[0])
#输出
if len(re2)==0:
    print()
else:
    min_,max_= re2[0]
    print(min_)
    print(max_)

发表于 2025-06-05 11:34:55 回复(0)
Python3
海洋游人头像 海洋游人
n = int(input())

# Overall logic (Read before proceeding to the solution):
# 1. Perform a floor division by 2 on the input (even) number denoted as n.
# 2. Gradually reduce the resultant number from step 1 by 1 and
#    check if the number is a prime number. Denote this number
#    as b.
# 2.1 If b is a prime number, then calculate c as: c = n - b
# 2.2 If c is is NOT a prime number, reduce b by 1 until it is a prime
#     number again.
# 3. This process terminates once both b and c are prime numbers. In other
#    words, suppose we write a while loop, then if EITHER b OR c is NOT a
#    a prime number, the while loop should keep going.

# Solution:
# First, you need write a function that checks whether an input integer
# is a prime number:

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        """
        Why do we take the square root of n here? Because if a factor that is
        larger than sqrt(n) exists (t), then there MUST BE another        
        factor that is SMALLER than sqrt(n) exists (s) such that
        s*t = n. Therefore, there is NO NEED to check beyond int(n**0.5)+1
        """
        if n%i == 0: # If any of the factors from i up to round(sqrt(n))+1
                     # can a factor of n, then n is NOT a prime number.
            return False
    return True

b = n // 2 # Start the value of b from the result of the floor division
           # of n by 2.
c = n - b

while not (is_prime(b) and is_prime(c)):
    b -= 1
    c = n - b

print(b)
print(c)
发表于 2025-04-04 00:49:00 回复(0)
Python3
实习_机器学习_广东或四川_5月中可入职头像 实习_机器学习_广东或四川_5月中可入职
n = int(input())
# print(n)
odd = []
def check(num):
    i = 2
    while i < num:
        if num % i == 0:
            return True
        i += 1
    return False
for i in range(2,n):
    if not check(i):
        odd.append(i)
a = 0
b = n
for num in odd:
    if n-num in odd:
        if abs(num-(n-num)) < b-a:
            a = min(num, n-num)
            b = max(num, n-num)
if a!=0:
    print(a)
    print(b)
else:
    print(-1)
    print(-1)
发表于 2025-03-25 15:15:03 回复(0)
Python3
好想去华为上班呀头像 好想去华为上班呀
#定义判断素数的函数
def is_sus(num):
    if num <2:
        return False
    for i in range(2,int(num**0.5)+1):
        if num%i==0:
            return False
    return True

#接收用户输入并初始化最小差值及ab的值
n= int(input())
minchazhi = float('inf')

a,b =0,0

#判断是否为素数，并判断差值的大小，循环遍历把最小的留下，并付给a和b
for i in range(n//2,1,-1):
    j=n-i
    if is_sus(i) and is_sus(j):
        chazhi = abs(i-j)
        if chazhi<minchazhi :
            minchazhi=chazhi
            a = min(i,j)
            b= max(i,j)
#输出结果
print(a)
print(b)
发表于 2025-02-24 17:40:54 回复(0)
Python3
牛客307634930号头像 牛客307634930号
def sushu(n):   #检查是否为素数
    if n == 1 or n == 0:
        return 0
    if n == 2:
        return 1
    i = 2
    while i < (n**0.5 +1) :
        if n % i != 0:
            i += 1
        else:
            return 0
    else:
        return 1
n = int(input())
li = [] #储存小于n的所有素数
su = [] #储存满足条件的素数
for i in range(n) :
    if sushu(i):
        li.append(i)
for i in li:
    if (n-i) in li:
        su.append(i)
l = len(su)
de = l // 2
for i in range(de): #删除su中前一半素数，剩下的第一个必为最小的
    del su[0]
print(n-su[0])
print(su[0])

发表于 2024-12-24 16:55:05 回复(0)
Python3
想和你写一辈子的bug头像 想和你写一辈子的bug
def is_prime(num):
    #检查数字是否为偶数
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def find_closest_prime_pair(n):
    #寻找偶数当中最接近的素数对
    for i in range(n // 2, 1, -1):
        if is_prime(i) and is_prime(n - i):
            return i, n - i

n = int(input().strip())

prime1, prime2 = find_closest_prime_pair(n)
print(prime1)
print(prime2)

发表于 2024-12-07 11:22:47 回复(0)
Python3
亲切的猕猴桃在吵架头像 亲切的猕猴桃在吵架 
aaa = int(input())
l=[]
def is_sushu(x):
    for i in range(2,x):
        if x%i == 0:
            return False
    return True

for i in range(2,aaa):
    j = []
    b = aaa - i
    if is_sushu(i) and is_sushu(b):
        j.extend([i,b])
    if len(j) ==2:
        j.sort()
        l.append(j)
# print(l)
l.sort(key=lambda x:x[1]-x[0])
print("\n".join(map(str,l[0])))

发表于 2024-10-02 21:53:35 回复(0)
Python3
年轻的嘟教授面向对象头像 年轻的嘟教授面向对象 
"""
1. 接收输入，转int
2. 定义函数，找素数
3. 找出最小素数
"""

def isPrimeNumber(num:int):
    i = 2
    while i <= num/2:
        if num % i == 0:
            return False
        i += 1
    return True


n = int(input())
res = (0,0)
for i in range(1, int(n/2)+1):
    tmp = 1000
    if isPrimeNumber(i) and isPrimeNumber(n-i):
        if abs(n-2*i) < tmp:
            res = i, n-i

print(res[0])
print(res[1])

发表于 2024-05-14 19:25:18 回复(0)
Python3
牛客916094558号头像 牛客916094558号
这就是简单的难度？
c = int(input())

# 检查c是否为偶数且大于等于4
if c % 2 != 0 or c < 4:
    print("请输入大于等于4的偶数")
else:
    prime_pairs = []  # 用于存储素数对的列表

    # 遍历可能的第一个素数a
    for a in range(2, c // 2 + 1):
        # 检查a是否为素数
        is_a_prime = all(a % i != 0 for i in range(2, int(a ** 0.5) + 1))
        if is_a_prime:
            # 计算第二个数b
            b = c - a
            # 检查b是否为素数
            is_b_prime = all(b % i != 0 for i in range(2, int(b ** 0.5) + 1))
            if is_b_prime:
                # 将素数对(a, b)添加到列表中
                prime_pairs.append((a, b))
                lst = min(prime_pairs, key=lambda x: x[1] - x[0])
                # 打印所有找到的素数对
                over = [i for i in lst]
    print(f"{over[0]}\n{over[1]}")
编辑于 2024-04-14 16:37:10 回复(0)
Python3
牛客425955392号头像 牛客425955392号
因为输入 n 为正偶数，可得知两个输出应该尽量接近 n // 2
因此，写一个function用来判断是否为质数，然后从n // 2开始，检查 left 和 right 是否为质数。否则继续向两边扩展。
代码： 
import math

n = int(input())

def is_prime(number: int) -> bool:
    if number < 2:
        return False
    elif number == 2:
        return True
    elif number % 2 == 0:
        return False

    sqrt_n = int(math.sqrt(number)) + 1
    for i in range(3, sqrt_n, 2):
        if number % i == 0:
            return False

    return True

left = n // 2
right = n // 2

while not is_prime(left)&nbs***bsp;not is_prime(right):
    left -= 1
    right += 1

print(str(left) + '\n' + str(right))


编辑于 2024-01-27 16:10:19 回复(0)
Python3
牛客1314520头像 牛客1314520
简单好理解，一个判断素数之后一个for判断最小
import math
def pdss(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i == 0:
            return False
    return True
zs = int(input())
min = zs-4
for i in range(2,zs//2+1):
    if pdss(i) and pdss(zs-i):
        if zs-2*i<=min:
            min = zs-2*i
            a = i
            b = zs-i
print(a)
print(b)
发表于 2023-11-18 19:56:57 回复(0)
Python3
牛客478833509号头像 牛客478833509号 
N = int(input())
primelist = [2,3]
res = []
for i in range(4,N):
    if i % 2 != 0:
        flag = 1
        for j in range(2,int(i/2)+1):
            if i % j == 0:
                flag = 0
                break
        if flag == 1:
                primelist.append(i)
for prime in primelist:
    n = N - prime
    if n in primelist and n >= prime:
        res.append((prime , n , n - prime))
for output in sorted(sorted(res, key= lambda x:x[2])[0][:-1]):
    print(output)

发表于 2023-09-20 18:58:53 回复(0)
Python3
牛客561675659号头像 牛客561675659号
from math import sqrt
import sys
def suhsu(num):
    for i in range(2,int(sqrt(int(num))+1)):
        if num%i==0:
            return False
    return True

for line in sys.stdin:
    a = line.strip()
    a=int(a)
    b=[]
    for i in range(1,a//2+1,2):
        b.append([i,a-i])
    b.insert(1,[2,a-2])
    c=b[::-1]
    #print(b)

    for i in c:
        if suhsu(i[0]) and suhsu(i[-1]):
            #输出
            for k in i:
                print(k)
            break

       

发表于 2023-08-31 13:39:51 回复(0)
Python3
Cyber2077头像 Cyber2077 
def is_prime(i):
    if i == 2:
        return True
    elif i % 2 == 1:
        for j in range(3, int(i**0.5)+1, 2):
            if i % j == 0:
                return False
        return True
    return False

n = int(input())
for i in range(n // 2, 1, -1):
    if is_prime(i) and is_prime(n - i):
        print(i, n - i, sep='\n')
        break

发表于 2023-07-07 13:02:18 回复(0)
Python3
danspace头像 danspace 
def isPrime(i):
    for j in range(2, i):
        if i % j == 0:
            return False 
    return True

n = int(input())
for i in range(n//2, 1, -1):
    # 检查是否为素数
    if isPrime(i) and isPrime(n-i):
        print(i, n-i, sep = '\n')
        break

发表于 2023-06-30 08:53:11 回复(0)
Python3
向明月_头像 向明月_
笨办法 
n=int(input())

def isss (x):
    for i in range(2,x//2+1):
        if x % i == 0:
            return 0
    return 1

ss=[]
t=[0]*2
diff=1000
for i in range(2,n+1):
    if isss(i)==1:
        ss.append(i)
# print(ss)
for x in ss:
    for y in ss:
        if x+y==n:
            if abs(x-y)<diff:
                diff=abs(x-y)
                t[0]=x
                t[1]=y
print(t[0])
print(t[1])


发表于 2023-06-17 21:12:43 回复(0)
Python3
天天i学习头像 天天i学习
def is_sushu(num):
    count = 0
    for i in range(2,num):
        if num%i == 0:
            count += 1
    if count == 0:
        return True
    else:
        return False
   
n = int(input())
m = int(n/2)
for i in range(m,n):
    if is_sushu(i):        
        if is_sushu(n-i):
            print(n-i)
            print(i)
            break
发表于 2023-06-07 17:30:07 回复(0)
提交观点

问题信息

穷举 基础数学 查找
难度：
44条回答 36535浏览

热门推荐

通过挑战的用户

查看代码

相关试题

查找组成一个偶数最接近的两个素数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号