首页 > 试题广场 >

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

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

热度指数：158582 时间限制：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

牛客564856240号

import sys 

def su(s):
    for i in range(n//2,n+1):
        for j in range(2,int(i**0.5)+1):
            if (i % j == 0)or((n-i) % j) == 0:
                break
        else:
            return i,n-i

for n in sys.stdin:
    n = int(n.strip())
    a,b = su(n)
    print(str(b)+'\n'+str(a))

发表于 2021-06-02 17:34:03 回复(0)

Python

三三不得酒吖

def sushu(x):
    for i in range(2,x):
        if x % i == 0:
            return False
    else:
        return True

while True:
    try:
        a = int(input())
        b = []
        for i in range(3,a//2 + 1):
            if sushu(int(i)) and sushu(int(a-i)):
                b.append([i,a-i])
        print(b[-1][0])
        print(b[-1][1])
    except:
        break

暴力破解

发表于 2021-05-26 22:57:33 回复(0)

Python

牛客诶谁

import sys


def func(n):
    if n <= 1:
        return False
    elif n == 2&nbs***bsp;n == 3:
        return True
    elif n % 2 == 0:
        return False
    else:
        for i in range(3, n, 2):
            if n % i == 0 and i**2 <= n:
                return False
        return True


for line in sys.stdin:
    num = int(line.strip())
    for i in range(num//2, 2, -1):
        if func(i) and func(num-i):
            print(i)
            print(num-i)
            break

发表于 2021-04-29 14:11:54 回复(0)

Python

牛客928445527号

def is_primer(num):
for i in range(2, num//2):
if num % i == 0:
return False
return True

while True:
try:
od = int(input())
li = range(od)
mid = od // 2
i = 1
if is_primer(li[mid]) and 2* li[mid] == od:
print(li[mid])
print(li[mid])
else:
while i <= mid:
lef = li[mid-i]
rig = li[mid+i]
if is_primer(lef) and is_primer(rig):
print(lef)
print(rig)
break
i +=1
except:
break

发表于 2021-04-09 14:54:19 回复(0)

Python

牛客622181604号

def is_p(num):
if num == 1:
return True
for i in range(2, int(num**0.5)+2):
if num % i == 0:
return False
return True

def close_p(num):
for i in range(int(num/2), 1, -1):
if is_p(i) and is_p(num-i):
return i, num-i

while True:
try:
num = int(input())
a, b = close_p(num)
print(a)
print(b)
except:
break

发表于 2021-04-05 15:05:27 回复(0)

Python

天君添桢

from math import sqrt

def is_prime(number):
    for i in range(2, round(sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

while True:
    try:
        even = int(input())
        i = j = even >> 1
        while i < even - 2:
            if is_prime(i) and is_prime(j):
                print(j)
                print(i)
                break
            i += 1
            j -= 1

    except:
        break

发表于 2021-03-18 13:35:44 回复(0)

Python

大溪地渔民

import sys


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


for n in sys.stdin:
    n = int(n)
    k = n//2 if n//2%2 else n//2-1
    for i in range(k, 0, -2):
        if is_prime(i) and is_prime(n-i):
            print(i)
            print(n-i)
            break

发表于 2020-12-17 21:33:59 回复(0)

Python

JeremyStar

def check_prime(num):
    for i in range(2, int(num**1/2)+1):
        if num % i == 0:
            return False
    return True


while True:
    try:
        even = int(input().strip())
        half = even // 2
        start = 0 if half % 2 == 1 else 1
        for i in range(start, half, 2):
            a, b = half + i, half - i
            if check_prime(a) and check_prime(b):
                print(b)
                print(a)
                break
    except:
        break

（1）选择从中间数开始，一加一减，保证和是输入数的同时，还达到了两个素数差值最小。（2）从奇数中寻找素数，每次跨度为2.

编辑于 2020-12-15 12:19:57 回复(0)

Python

小菜_

def isPrime(n):
    for i in range (2, n):
        if n%i == 0:
            return False
    return True #注意位置
while True:
    try:
        n = int(input())//2
        start = 1
        if n%2 == 1:
            start = 0
        for i in range (start, n, 2):
            a, b = n+i, n-i
            if isPrime(a) and isPrime(b):
                print(b)
                print(a)
                break
        else:
            break
    except:
        break

发表于 2020-12-14 19:58:11 回复(0)

Python

乐观的lishan

# 2020年11月19日23:26:15
# 判断一个数是否为素数
def prime(num):
    for i in range(2,int(num**(1/2))+1):
        if num%i==0:
            return False
    return True
while True:
    try:
        n = int(input())
        for i in range(n>>1,n):
            if prime(i) and prime(n-i):
                print(n-i)
                print(i)
                break
    except:
        break

编辑于 2020-11-19 23:44:56 回复(0)

Python

gu_xing

def is_su(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    else:
        return True

while True:
    try:
        n = int(input())
        s = list(filter(is_su, [j for j in range(2, n)]))
        x1, x2 = 0, 0
        for k in s:
            if (n - k) in s and n-k >= k:
                x1, x2 = k, n-k
        print(x1)
        print(x2)

    except:
        break

发表于 2020-08-18 12:24:17 回复(0)

Python

无双19950516

一定要注意边界值，比如 582对应的答案是 281 281

否则通过率只有70%

发表于 2020-07-27 22:43:00 回复(0)

Python

君临天下201804050931706

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

while True:
    try:
        n = int(input())
        minP = 0
        maxP = n
        for i in range(2,int(n/2)+1):
            if isPrime(i) and isPrime(n-i) and (n-i-i)<(maxP-minP):
                minP = i
                maxP = n-i

        print(minP)
        print(maxP)

    except:
        break

发表于 2020-07-14 09:21:24 回复(0)

Python

求一个offer啊😊

def zhishu(n):
    number = []
    for i in range(2,n):
        for j in range(2,i):
            if (i % j) == 0:
                break
        else:
            number.append(i)
    return number

while True:
    try:
        n = int(input())
        number = zhishu(n)
        minv=n
        res=[]
        for i in number:
            if n-i in number:
                minv = min(minv,abs(n-i-i))
                if minv == abs(n-i-i):
                    res = [i,n-i]
        print(res[1])
        print(res[0])
    except:
        break

发表于 2020-07-09 22:23:35 回复(0)

Python

敢梦敢当

python;有注释

# 素数就是质数，就是除了1和它本身以外不再有其他的因数
# 判断某一个数是不是素数 https://wenku.baidu.com/view/f3d19275b90d6c85ed3ac600.html

# 判断一个数是否为素数-函数
def sy(n):
    if n%2==0: # 如果该数能被2整除，则不是素数
        return 0
    for x in range(3, int(n**0.5)+1, 2): 
        # 从3开始判断到sqrt(m)+1即可(包括m**0.5的整数部分这个值)，步长为2
        # 因为一个数开平方后的数是这个数的最大因子，之后的数就不用判断了
        if n%x==0: # 如果这个数能被x整除
            return 0
    return 1

while True:
    try:
        lstSS = [1] # 素数表，起码有1
        num = int(input()) # 输入一个偶数
        # 遍历num，得到小于num的所有素数列表（num是偶数，肯定不是素数，就不遍历到num+1了）
        for i in range(3, num): # 对应判断函数，从3开始
            # 判断i是否为素数
            if sy(i):
                lstSS.append(i)

        # 遍历素数表，如果有lstSS[i] + lstSS[j] == num则记录
        lst2 = [] # 把两素数差值和素数对作为元组加入到列表中
        for i in range(len(lstSS)):
            for j in range(i, len(lstSS)):
                if lstSS[i] + lstSS[j] ==  num:
                    lst2.append((lstSS[j]-lstSS[i], str(lstSS[i])+' '+str(lstSS[j])))
        lst2.sort(key = lambda i:i[0], reverse=False)
        s1, s2 = lst2[0][1].split() # 得到两个元素
        print(s1) # lstSS[i]
        print(s2) # lstSS[j]
    except:
        break

发表于 2020-07-05 12:14:45 回复(0)

Python

最爱大麦茶

import math
def primesqrt(n):
    result = list()
    result.append(2)
    result.append(3)
    for i in range(5,n+1,2):
        for j in range(2,int(math.sqrt(i))+2):
            if i%j == 0:
                break
        else:
            result.append(i)
    return result

while True:
    try:
        N = int(input())
        res = []
        zhishu_list = primesqrt(N)
        mindiff = float('inf')
        for i in zhishu_list:
            if N-i in zhishu_list:
                mindiff = min(mindiff,abs(N-i-i))
                if mindiff == abs(N-i-i):
                    res = [i,N-i]
        print(res[1])
        print(res[0])
    except:
        break

发表于 2020-06-12 00:46:07 回复(0)

Python

心怀高远，脚踏实地

def isprime(n : int) -> bool:
    if n%2 == 0:
        return False
    elif n%3 == 0:
        return False
    elif n%5 == 0:
        return False    
    for i in range(2,n//5+1,1):
        if n%i == 0:
            return False 
    return True            
while 1:
    try:
        N = int(input())
        for i in range(N//2,N,1):
            if isprime(i):
                if isprime(N-i):
                    print(N-i)
                    print(i)
                    break
    except:
        break

可以从中值开始递增获取素数对

发表于 2020-05-07 22:16:25 回复(0)

Python

牛客477050091号

def prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

while True:
    try:
        n = int(input())
        s = n // 2
        for k in range(s,2,-1):
            if prime(k):
                if prime(n-k):
                    print(k)
                    print(n-k)
                    break
    except:
        break

发表于 2020-04-26 16:24:58 回复(0)