33分求助

jywa @ 2024-08-18 20:04:57

#include<bits/stdc++.h>
using namespace std;

bool isPrime(int n){
    if(n==0||n==1)return 0;
    else{
        for(int i=2;i<n;i++){
            if(n%i==0)return 0;
        }return 1;
    } 
}

bool isPalindrome(int num){
    int p=num;  
    int k=0;
    while(p!=0) {
        k=k*10+p%10;
        p=p/10;
    }if(k==num)return 1;
    else return 0;    
}

int main(){
    int a,b; 
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        if(isPrime(i)&&isPalindrome(i))printf("%d\n",i);
    }return 0;
}

by Mzh2012 @ 2024-08-18 20:07:58

@jywa 数据范围1亿，太大了你的代码时间复杂度太高了

by jywa @ 2024-08-18 20:10:14

@Mzh2012 那怎么改能对？大佬，我看他们讨论说要用打表？ 这么改还是不对(刚才想起来b不能比a小)

#include<bits/stdc++.h>
using namespace std;

bool isPrime(int n){
    if(n==0||n==1)return 0;
    else{
        for(int i=2;i<n;i++){
            if(n%i==0)return 0;
        }return 1;
    } 
}

bool isPalindrome(int num){
    int p=num;  
    int k=0;
    while(p!=0) {
        k=k*10+p%10;
        p=p/10;
    }if(k==num)return 1;
    else return 0;    
}

int main(){
    int a,b; 
    cin>>a>>b;
    if(b<a)swap(a,b);
    for(int i=a;i<=b;i++){
        if(isPrime(i)&&isPalindrome(i))printf("%d\n",i);
    }return 0;
}

请大佬指点

by Mzh2012 @ 2024-08-18 20:14:50

@jywa 可以打表 我也是打表，但你的代码打表的话可能要打好久，要先优化一下判断素数再打表。

by Mzh2012 @ 2024-08-18 20:15:50

@jywa 把

bool isPrime(int n){
    if(n==0||n==1)return 0;
    else{
        for(int i=2;i<n;i++){
            if(n%i==0)return 0;
        }return 1;
    } 
}

换成

bool isPrime(int n){
    if(n==0||n==1)return 0;
    else{
        for(int i=2;i*i<=n;i++){
            if(n%i==0)return 0;
        }return 1;
    } 
}

就可以开始打表了。

by Mzh2012 @ 2024-08-18 20:17:55

@jywa 如果你不想打表的话可以去看看题解是怎么优化的。

by jywa @ 2024-08-18 20:18:44

那大佬您看这样行不行？他们说要加上：

if(b>100000000)b=100000000;

然后将类型改为long long?

#include<bits/stdc++.h>
using namespace std;

bool isPrime(long long n){
    if(n==0||n==1)return 0;
    else{
        for(long long i=2;i<n;i++){
            if(n%i==0)return 0;
        }return 1;
    } 
}

bool isPalindrome(long long num){
    long long p=num;  
    long long k=0;
    while(p!=0) {
        k=k*10+p%10;
        p=p/10;
    }if(k==num)return 1;
    else return 0;    
}

int main(){
    long long a,b; 
    cin>>a>>b;
    if(b<a)swap(a,b);
    if(b>100000000)b=100000000;
    for(long long i=a;i<=b;i++){
        if(isPrime(i)&&isPalindrome(i))printf("%d\n",i);
    }return 0;
}

以大佬怎么看？还请多多指教。

by jywa @ 2024-08-18 20:20:47

@Mzh2012 大佬，我样例试过了……但放进去只有33分，7个TLE，TLE是啥意思？是超时吗？

by Mzh2012 @ 2024-08-18 20:22:30

@jywa 这不一样的吗，题目不是说了 b \leq 100000000 吗？ 开不开 long long是一样的， 还是看看题解则么优化的吧。

by Mzh2012 @ 2024-08-18 20:22:51

@jywa TLE 是超时

by Emil_ @ 2024-08-18 20:22:59

@jywa ac代码：挺好理解的，先判回文后判质数

#include<bits/stdc++.h>
using namespace std;
bool huiwen(int n){
    bool r=true;
    int w[15]={};
    int k=1;
    while(n>0){
        w[k]=n%10;
        k++;
        n/=10;
    }
    for(int i=1;i<=k;i++){
        if(w[i]!=w[k-i]){
            r=false;
        }
    }
    return r;
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); 
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        if(i%2==0){
            i++;
        }
        if(huiwen(i)==true){
            bool f=true;
            for(int j=2;j<=sqrt(i);j++){
                if(i%j==0)
                    f=false;
            }
            if(f)
                cout<<i<<endl;
        }
    }
    return 0;
}

求关qwq