python - 如何优化和寻找大量输入的输出？

Question

对于输入号码N , 我试图找到特殊对的数量 (x,y)满足以下条件:

• x != y
• 1 <= N <= 10^50
• 0 <= x <= N
• 0 <= y <= N
• F(x) + F(y)是素数，其中 F是数字所有数字的总和

最后打印计数模1000000007的输出

---

示例输入: 2

示例输出: 2

说明:

• (0,2) Since F(0)+F(2)=2 which is prime
• (1,2) Since F(1)+F(2)=3 which is prime
• (2,1) is not considered as (1,2) is same as (2,1)

我的代码是:

def mod(x,y,p):
    res=1
    x=x%p
    while(y>0):
        if((y&1)==1):
            res=(res*x)%p
        y=y>>1
        x=(x*x)%p
    return res

def sod(x):
    a=str(x)
    res=0
    for i in range(len(a)):
        res+=int(a[i])
    return res

def prime(x):
    p=0
    if(x==1 or x==0):
        return False
    if(x==2):
        return True
    else:
        for i in range(2,(x//2)+1):
            if(x%i==0):
                p+=1
        if(p==0):
            return (True)
        else:
            return(False)

n=int(input())
res=[]
for i in range (n+1):
    for j in range(i,n+1):
        if(prime(sod(int(i))+sod(int(j)))):
            if([i,j]!=[j,i]):
                if([j,i] not in res):
                    res.append([i,j])
count=len(res)
a=mod(count,1,(10**9)+7)
print(res)
print(a)

我期望 9997260736 的输出成为671653298但错误是代码执行超时。

Answer 1

已经发布了有点太长的评论，所以将其更改为回答:

在考虑此类问题时，不要将问题直接转化为代码，而是看看您只能做一次或以不同的顺序做些什么。

截至目前，您正在执行 N*N通过，每次计算 x 和 y 的数字总和(还不错)并分解每个总和以检查它是否为素数(真的很糟糕)。这意味着总和 s你在检查它是否是素数 s+1次! (对于 0+s、1+(s-1)、...、(s-1)+1、s+0)。

您可以做什么不同的事情？

让我们看看我们知道什么:

• 许多数字的数字总和是相同的。

• 对于许多值，sod(x) 和 sod(y) 的总和是相同的。

• 数字在其第一次和第 n 次检查期间为质数(并且检查它是否为质数的成本很高)。

所以最好只计算一次质数，并且每个和只计算一次。但是当我们有很多数字时该怎么做呢？

换个思路:得到质数，将其拆分为两个数(sodx和sody)，然后从这些数生成x和y。

例子:

总理 p = 7 .给出可能的总和为 0+7、1+6、2+5、3+4。

然后对于每个总和，您可以生成一个数字，例如对于 N=101 和 sod=1，您有 1、10、100，对于 sod=2，您有 2、11、20、101。您可以存储它，但生成它应该不会那么糟糕。

其他优化:

你必须考虑如何使用你的 N 来限制生成质数:

给定 N 的 lenN 个数字(记住，lenN 是 ~log(N))，可能的最大数字和是 9*lenN(对于仅由 9 组成的 N)。这意味着我们的 sodx 和 sody <= 9*lenN，所以素数 p = sodx + sody <= 18*lenN

看:这意味着 18*lenN 检查数字是否为质数与 N*N 检查您以前的算法有!