Skip to main content
 首页 » 编程设计

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

2024年11月24日9davidwang456

对于输入号码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但错误是代码执行超时。

请您参考如下方法:

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

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

截至目前,您正在执行 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 检查您以前的算法有!