函数正确,答案全错(气)

P1217 [USACO1.5] 回文质数 Prime Palindromes

wzy091030 @ 2023-04-03 17:21:31

#include <bits/stdc++.h>
using namespace std;
bool sh(int a){
    for(int i=2;i<(a/2+1);i++){
        if (a%i==0) return false;
    }
    return true;
}
bool ac(int a)
{int sum=0,q;
    while(a>1)
    {
        q=a%10;
        a=a-q;
        a=a/10;
        sum=sum*10+q;
    }
    if(sum==a)
    return true;
    else
    return false;
}
int main()
{
    int m,n;
    cin>>m>>n;
    for(int i=m;i<n;i++)
    {
        if(sh(i)==1&&ac(i)==1)
        cout<<i<<endl;
    }
    return 0;
}

要疯了!!!!!!!!!!!!!!!!!!!!!!


by 2011FYCCCTA @ 2023-04-03 17:28:30

你判断回文的函数的这一行有误:

if(sum==a)
    return true;

因为你在拆位时将a都除了,此时的a都变成1了。

还有这里:

while(a>1)

应该是a>0吧


by _zzzzzzy_ @ 2023-04-03 17:29:48

@wzy091030 我建议正确性的问题解决之后把判断回文和素数的函数位置换一下,因为判断回文的复杂度是 O(\log n)


by 2011FYCCCTA @ 2023-04-03 17:30:47

还有这行:

for(int i=m;i<n;i++)

应该是要遍历到n吧


by 2011FYCCCTA @ 2023-04-03 17:33:01

还有个小优化:判断质数时只要遍历到i*i<=n 就行了


|