首页 > 试题广场 >

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

[编程题]查找组成一个偶数最接近的两个素数

热度指数：162483 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的偶数 $n$ ，找出两个素数 $a,b$ ，满足：
$\hspace{23pt}\bullet\,$ 它们的和等于 $n$ ；
$\hspace{23pt}\bullet\,$ 它们的差值的绝对值最小。

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

输入描述:

输入一个整数 。保证  是偶数。

输出描述:

第一行输出一个整数 ，代表满足条件的素数对中的较小者。
第二行输出一个整数 ，代表满足条件的素数对中的较大者。

示例1

输入

输出

7
13

示例2

输入

输出

2
2

算法知识视频讲解

Python 3

牛客927606361号

def prime(n): #筛选素数
    sum = 0
    if n > 1:
        for i in range(1,n+1):
            if n % i == 0:
                sum += 1
        if sum == 2:
            return True

n = int(input())
l = []   #存储所有的素数因数
for i in range(2,n//2+1): #从2开始遍历，到n的一半
    if prime(i) and prime(n-i): #如果i和n-i都是素数，则作为一个元祖加入到列表l中
       l.append((i,n-i))
s = l[0]
m = l[0][1] - l[0][0] 
for i in range(1,len(l)):  #判断所有素数因数中差值最小的
    if l[i][1] - l[i][0] <= m:
        s = l[i]
        m = l[i][1] - l[i][0]
for v in s:
    print(v)

发表于 2025-04-15 15:12:44 回复(0)

Python 3

bry716

import math
def check(num):
    if num == 1:
        return False
    elif num == 2:
        return True
    else:
        for i in range(2,int(math.sqrt(num))+1):
            if num%i == 0:
                return False
    return True


while True:
    try:
        n = int(input())
        l = [-1]*3
        for i in range(2,n//2+1):
            if check(i) and check(n-i):
                if l[2] < 0:
                    l[0] = i
                    l[1] = n-i
                    l[2] = n - 2*i
                elif l[2] >= 0 and (n-2*i) < l[2]:
                    l[0] = i
                    l[1] = n-i
                    l[2] = n - 2*i
        print(l[0])
        print(l[1])
    except:
        break

发表于 2024-06-05 15:33:49 回复(0)

Python 3

zackw

import math

def is_prime(num: int) -> bool:
    if num < 2:
        return False
    elif num == 2:
        return True
    else:
        for i in range(2, math.ceil(num**0.5 + 1)):
            if num % i == 0:
                return False
        return True


n = int(input())
min_pair = [0,n]
min_value = n
for i in range(2, int(n / 2)+1):
    if is_prime(i) and is_prime(n - i):
        if n - i - i < min_value:
            min_value = n - i - i
            min_pair = [i, n - i]
print(min_pair[0])
print(min_pair[1])

发表于 2023-09-28 16:17:34 回复(0)

Python 3

再多看一眼就会爆炸

import math
a=int(input())
c=[]
d={}
for i in range(2,a+1):
    b=[]
    for j in range(1,int(math.sqrt(i))+1):
        if i%j==0:
            b.append(i//j)
            b.append(j)
        if j==int(math.sqrt(i)) and len(b)==2:
            c.append(i)
for k in range(0,len(c)):
    for l in range(k,len(c)):
        if c[k]+c[l]==a:
            d[(k,l)]=c[l]-c[k]
e=sorted(d.keys(),key=lambda x : x[1])
print(c[e[0][0]])
print(c[e[0][1]])

发表于 2023-03-04 04:27:11 回复(0)

Python 3

牛客527980301号

import math
def su(m):
if m <= 1:
return False
elif m == 2:
return True
else:
for i in range(2,int(math.sqrt(m))+1):
if m % i == 0:
return False
break
return True

while True:
try:
n = int(input())
for j in range(n//2,n):
if su(j) and su(n-j):
print(n-j)
print(j)
break
except:

break

发表于 2022-09-10 06:55:14 回复(0)

Python 3

牛客597557718号

import math
def isPrime(num):
    if num == 2:
        return True
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

while True:
    try:
        n = int(input())
        # 从中位数到2递减，第一次发现两个素数相加等于输入即为所求
        for i in range(n//2, 2, -1):
            # i不是素数，继续下一次循环
            if not isPrime(i):
                continue
            # i是素数
            else:
                # 判断n-i是否为素数，如果是，打印
                if isPrime(n-i):
                    print(i)
                    print(n-i)
                    break
    except:
        break

发表于 2022-09-07 17:16:23 回复(0)

Python 3

649924619

def checknum(num):
    if num == 1:
        return False
    if num == 2:
        return True
    list0 = []
    for i in range(2,num):
        if num % i == 0:
            list0.append(i)
    if not list0:
        return True
    else:
        return False
    
while True:
    try:
        n = int(input())
        num = n // 2
        for i in range(num):
            a,b = num -i,num+i
            if checknum(a) and checknum(b):
                print(a)
                print(b)
                break
    except:
        break

发表于 2022-08-06 12:56:50 回复(0)

Python 3

牛客245788614号

#检查数字是不是素数
def check_num(n):
if n == 2 :
return True
for i in range(2,n):
if n % i == 0:
# print(n)
return False

# print(n)
return True

#找出最小差值的素数对
def find_min(m):
if m % 2 != 0:
return 0

else:
output = ''
min_gap = m
for i in range(0,int(m/2)):
a = int((m/2) - i)
b = int((m/2) + i)
# print(a,b)
# print(a,check_num(a))
if check_num(a) and check_num(b):
gap = abs(a-b)
if gap < min_gap :
output = ''
min_gap = gap
output = str(a) + '\n' + str(b)
return output

print(find_min(int(input())))

发表于 2022-08-01 00:07:32 回复(0)

Python 3

AlexLyn_00

python3 def isPrime

def isPrime(number):
    if number == 2:
        return True
    limited = int(number**0.5+2)
    for i in range(2, limited):
        if number % i == 0:
            return False
    return True

while True:
    try:
        number = int(input())
        output_1, output_2 = int(number/2), int(number/2)
        while True:
            sign_1 = isPrime(output_1)
            sign_2 = isPrime(output_2)
            if sign_1*sign_2==1:
                break
            output_1 -= 1
            output_2 += 1
        print(output_1)
        print(output_2)
        
    except:
        break

发表于 2022-07-18 18:08:39 回复(0)

Python 3

易木听风

def isprime(n):
for i in range(2,n):
if n%i == 0:
return False
return True
while True:
try:
n = int(input())
for i in range(int(n/2+1)):
if isprime(i) and isprime(n-i):
# print(i, ' ', n-i)
sign = i
print(sign)
print(n-sign)
except:
break

发表于 2022-07-11 23:29:44 回复(0)

Python 3

牛客465765863号

def f(x): # 写一个函数，用来判断素数
	if x <= 1:return False # 1既不是素数，也不是合数
	elif x == 2:return True #2是素数 #return之后的代码不会执行
	else:
		for i in range(2,int(x**0.5)+1): #节约时间
			if x%i == 0:return False #不是素数
		else:return True #是素数

n = int(input()) # n是偶数
for i in range(int(n/2),1,-1): #n/2是偶数，从 n/2-1 开始遍历，找第1对即可
    if f(i) and f(n-i):
        print(i) # i越来越小，所以i一定小于n-1
        print(n-i);break

发表于 2022-06-18 21:29:54 回复(0)

Python 3

牛客村-村长

def su(num):  #判断该数是否为素数
    a = []
    for i in range(1,num+1):
        if num%i == 0:
            a.append(i)
    if len(a) == 2:
        return 1
    else:
        return -1

while True:
    try:
        n = int(input())
        a = []
        for i in range(2,n):   #从2开始，有序递增，产生的素数也是从小到大排列好的
            num = i
            if su(num) == 1: #该数为素数时
                a.append(i)  #所有素数放入列表a
        b = []
        for i in range(len(a)):
            if (n-a[i]) in a:  #筛选出两数只和为n的情况
                if a[i] > n//2: #去除后半段重复的数据
                    break
                b.append(a[i])  #满足条件的数据放入新的列表，因为数据为有序数据，最后一组则为最佳答案

        print(b[len(b)-1])
        print(n-b[len(b)-1])

    except:
        break

#常规方法，好理解些

发表于 2022-06-09 17:37:26 回复(0)

Python 3

牛客784944519号

有谁写的比我更复杂吗？

def primeNum(n):

    if n == 2:
        return True
    elif n == 0 or n == 1:
        return False
    else:
        beiChuShu = []
        for i in range(2,n):
            if n % i == 0:
                beiChuShu.append(i)
        if len(beiChuShu) == 0:
            return True
        else:
            return False
while True:
    try:
        ouShu = int(input())
        primeCha = []
        primeChaInt = []
        minPrime = []
        minPrimeList = []
        for i in range(2,ouShu):
            for x in range(i,ouShu):
                if i + x == ouShu and primeNum(i) and primeNum(x):
                    primeCha.append(f'{x}-{i}')
                    primeChaInt.append(x-i)
        for m in primeCha:
            if eval(m) == min(primeChaInt):
                minPrime = m.split('-')
                # minPrime.sort()
#                 print(minPrime)
                for q in minPrime:
                    minPrimeList.append(int(q))
                minPrimeList.sort()
                for p in minPrimeList:
                    print(p)
    except:
        break

发表于 2022-06-07 00:56:42 回复(0)

Python 3

小何努力打怪升级

最笨的方法：

num=int(input())

list1=[]
dict={}
list2=[]
for i in range(1,num):
time=0
for x in range(1,i+1):
if i%x==0:
time+=1
if time==2:
list1.append(x)
for j in list1:
for k in list1:
if int(j)+int(k)==num:
dict[j]=k

for z,x in dict.items():
if x-z>=0 :
a=x-z
list2.append(a)
b=min(list2)
for z,x in dict.items():
if x-z==b:
print(z)
print(x)

发表于 2022-05-28 16:26:56 回复(0)

Python 3

牛客939492338号

奇数加奇数才能是偶数，偶数加偶数，肯定不可能都是素数

所以先从中间向两边查找，step=2保证都是奇数

如果给定的数n是4的倍数，n/2是偶数，则这两个数应该是(n/2-1,n/2+1),(n/2-2,n/2+3)...

如果不是，则n/2就是奇数，则这两个数就是(n/2-2,n/2+2),(n/2-4,n/2+4)

再判断是否是素数输出就行了

发表于 2022-05-14 15:17:54 回复(0)

Python 3

HeartBeating

def isPrime(n): #判断是否是 素数
    if n == 2:
        return True
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

n = int(input()) # 输入n=20
prime = [] #所有素数 组成的列表
for i in range(2,n//2+1): #取整除 - 返回商的整数部分（向下取整）9//2=4,,,-9//2=-5
    if isPrime(i): #是素数
        #prime = prime + [i]
        prime.append(i)
         
prime.sort(reverse=True) # 大小排序 [7, 5, 3, 2]
#print(prime)
for i in prime:
    if isPrime(n-i): # 输出两个素数差值最小的素数对
        print(i) # 7
        print(n-i)# 13
        break

发表于 2022-05-04 03:17:51 回复(0)