2 cattle knife cattle_knife 于 2017.09.03 16:57 提问

PAT乙级1007.素数对猜想,Python运行超时

图片说明
以下是我的代码:

l = int(input())
first = 2
cnt = 0
i = 3
while i < l+1:
    j = 2
    while j <= i**0.5:
        if i % j == 0:
            break
        if j == 2:
            j += 1
        else:
            j += 2
    else:
        if i - first == 2:
            cnt += 1
        first = i
    i += 2
print(cnt)

图片说明
希望大佬能指出我的问题,最好可以修改我的源代码

3个回答

caozhy
caozhy   Ds   Rxr 2017.09.03 17:35
cattle_knife
cattle_knife 我们方法不都差不多吗,为什么我没有成功,我的代码有什么问题吗
3 个月之前 回复
yxpandjay
yxpandjay   2017.09.03 18:35

存在大量重复计算。你先把题意范围内的素数全算出来,在比较相邻的多好

cattle_knife
cattle_knife 那样还是超时,我就是因为分开来做超时,才合并去做的,而且我不认为有重复计算,希望你详细能指出问题在哪
3 个月之前 回复
van_brilliant
van_brilliant   2017.09.04 21:24

#include
int main(void)
{

int max;
scanf("%d",&max);
int a[max];
a[0]=2;
int output=0;
int index=1;
int i,j;
for (i = 2; i <= max; i++) {
if ((i>2)&&(i%2==0)) {
continue;
}
for ( j = i-1; j >0; j--) {
if (j==1) {
a[index]=i;
index++;
}
if (i%j==0) {
break;
}
}
}
for (i = 0; i < index-1; i++) {
if ((a[i+1]-a[i])==2) {
output++;
}
}
printf("%d",output);
return 0;
}
我也是最后一个测试点超时,这是我的C代码

Csdn user default icon
上传中...
上传图片
插入图片