为什么我的程序需要这么长时间才能执行/我完成问题的方式有问题吗?

Question

我目前正在研究这个问题:

对于各种给定的正整数N>3，找出两个质数A和B使得N是平均值(A + B)的均值，即N = (A + B)/2。回想一下，素数是一个整数P>1只能被1和p整除，例如，2、3、5、7、11是前几个素数，4、6、8、9不是素数。

输入规范

输入的第一行是数字T(1≤T≤1000)，这是测试用例的数量。每个人后面的T行包含一个整数N(4≤Ni≤1 000 000,1≤i≤T)。15分中的6分，都是N <000 .

输出规范

输出将由T行组成。带有的行输出将包含两个整数A和B，用一个空格隔开。它应该是N = (A + B)/2并且A和B是素数数字。如果对于一个特定的N有多于一个可能的A和B，输出任意这样的一对。订单"艾"one_answers"毕"这一对的关系并不重要。对于任意给定的n，总是存在至少一组值A和B

下面是我的代码:

numofInput = int(input())
primeSet = []
for i in range(numofInput):
line = input()
primeSet.append(line)
print("Starting...")
for i in primeSet:
for j in range(4, 1000):
if (j / 2 != 0) and (j / 3 != 0) and (j / 5 != 0) and (j / 7!= 0) and (j / 11 != 0):
num1 = j
for k in range(4, 1000):
if (k / 2 != 0) and (k / 3 != 0) and (k / 5 != 0) and (k / 7!= 0) and (k / 11 != 0):
num2 = k
if ((num1 + num2) / 2) == i:
print(num1 + num2)
else:
continue

现在我真的不知道是怎么回事，我会感谢任何帮助!提前感谢!

New For循环代码:

for i in primeSet:

for j in range(4, 1000000):
if (j / 2 != 0) and (j / 3 != 0) and (j / 5 != 0) and (j / 7!= 0) and (j / 11 != 0):
num1 = j
num2 = i - j
if ((num1 + num2) / 2) == i
print(num1, num2)
else:
continue

Answer 1

这个问题是Golbach猜想的一个变体，该猜想指出所有偶数都可以表示为两个素数的和。所以，如果你找到两个质数加起来等于2N，你就有答案了。

找到它们的最快方法是建立一组素数，并检查每个素数与2N的差是否也是素数。使用集合将使验证非常快。

所以你需要一个质数生成器(例如使用埃拉托色尼筛子)来构建你的质数集，然后通过它们一直运行到n。

def genPrimes(N):
isPrime = [True]*(N+1)
yield 2
for p in range(3,N+1,2):
if not isPrime[p]: continue
yield p
isPrime[p*p::p] = (False for _ in range(p*p,N+1,p))

def goldbach(Even):
primes = {*genPrimes(Even)} # set of primes that can add up to Even
for p in primes:
if 2*p>Even: break    # only primes up to half of Even (avoids duplicates)
if Even-p in primes:  # when the difference with Even is also a prime
yield p,Even-p    # return the two primes

使用例子:

N = 50
print(*goldbach(2*N))
# (3, 97) (11, 89) (17, 83) (29, 71) (41, 59) (47, 53)    

Answer 2

Eratosenes筛的示范

def find_primes(n):
''' Use Sieve of Eratosthenes to find primes up to n 
Code from https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Using_set_lookup
'''
multiples = set()
for i in range(2, n+1):
if i not in multiples:
yield i
multiples.update(range(i*i, n+1, i))

def find_a_b(n, primes = set(find_primes(2000000))):
'''
finds two numbers a, b such that a and b are primes and a + b == 2*n
Default argument primes will be initialized once the first time function is called
''' 
n = 2*n # avoid division by looking for A + B = 2*n 
# rather than n = (A + B)/2
for A in primes:
if A < n and n - A in primes:
return A, n - A  # solution as a tuple
return None  # No solution

# Test Run on test cases (using numbers 5 to 100)
numofInput = int(input())
primeSet = []
for i in range(numofInput):
line = int(input())  # OP code missing int conversion
primeSet.append(line)

for i in primeSet:
sol = find_a_b(i)
if sol:
# There was a solution
print(f'{i} == ({sol[0]} + {sol[1]})/2')

输入>

2
5
6

5 == (3 + 7)/2
6 == (5 + 7)/2

替代素数查找算法

def find_primes_prime_division(n):
' find primes from 2 up to n '
primes = [2, 3] # seed with first two primes
test = primes[-1]
while test < n:
test += 2
if all(test % p for p in primes):
primes.append(test)  # test is prime since no divisors
return primes