大佬们能不能帮忙看一下我的思路哪里出现了问题QAQ

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

wvvvvvvvvvvvv @ 2024-03-25 18:30:55

#include<stdio.h>
#include <stdbool.h>
bool ispa(int x) //判断回文数的函数
{
    int num[20];
    int n = 0;
    int i = 0;
    while (x > 0)//用数组储存每一位数
    {
        num[i] = x % 10;
        x /= 10;
        n++;//用来统计这个数有几位
        i++;
    }
    if (num[i] == num[n -1- i])//判断回文数 是就返回true 不是就返回false
        return true;
    else
        return false;
}
bool ispr(int x) //判断质数的函数
{
    int i;
    int num = 0;
    for (i = 1; (i * i) <= x; i++)
    {
        num += (x % i == 0) ? 1 : 0;
    }
    if ((num - 1) == 0)//除去1后判断有没有因数 是就返回true 否就返回false
        return true;
    else
        return false;
}
int main() //主函数
{
    int a, b, i;
    bool pa = false;//初始化pa pr为false
    bool pr = false;
    scanf_s("%d %d", &a, &b);
    for (i = a; ((i % 2) != 0) && i <= b; i++)//偶数一定不是质数，缩小范围（a一定大于等于5 所以不需要考虑2）
    {
        pa = ispa(i);//判断回文数
        if (pa)//是回文数就再判断是不是质数
            pr = ispr(i);
        if (pr)//是质数就输出
            printf("%d\n", i);
        pa = false;//重置pa和pr
        pr = false;
    }
    return 0;
}

by lunjiahao @ 2024-03-25 19:10:13

超时了，时间复杂度为 O(n \times (\sqrt n +\log_{10}n))=O(n \sqrt n +n \log_{10}n)

by lunjiahao @ 2024-03-25 19:16:52

@wvvvvvvvvvvvv 可以优化一下 for 循环的终止条件和每次改变的值

将 for (i = a; ((i % 2) != 0) && i <= b; i++)

改为

if(a==2) printf("%d\n",a);
if(a%2==0) a++;
if(b>9999999) b=9999999;
for (i = a; i <= b; i+=2)

可以稍微降一点复杂度

by wvvvvvvvvvvvv @ 2024-03-25 19:26:32

@lunjiahao 可是结果全是WA 不是TLE诶... 脑子已经晕了...

by lunjiahao @ 2024-03-25 19:31:42

@wvvvvvvvvvvvv

不是你回文都打错了啊……

by lunjiahao @ 2024-03-25 19:34:46

code:

#include<stdio.h>
#include <stdbool.h>
bool ispa(int x) //判断回文数的函数
{
    int num[20];
    int n = 0;
    while (x)//用数组储存每一位数
    {
        num[++n] = x % 10;
        x /= 10;
    }
    for(int i=1,j=n;i<j;i++,j--)
        if(num[i]^num[j]) return false;
    return true;
}
bool ispr(int x) //判断质数的函数
{
    int i;
    for(i=2;i*i<=x;i++)
        if(x%i==0) return false;
    if(x<=1) return false;
    return true;
}
int main() //主函数
{
    int a, b;
    bool pa = false;//初始化pa pr为false
    bool pr = false;
    scanf("%d %d", &a, &b);
    if(a==2) printf("%d\n",a);
    if(!(a&1)) a++;
    if(b>9999999) b=9999999;
    for (int i = a;i <= b; i+=2)//偶数一定不是质数，缩小范围（a一定大于等于5 所以不需要考虑2）
    {
        pa = ispa(i);//判断回文数
        if (pa)//是回文数就再判断是不是质数
            pr = ispr(i);
        if (pr)//是质数就输出
            printf("%d\n",i);
        pa = false;//重置pa和pr
        pr = false;
    }
    return 0;
}

by wvvvvvvvvvvvv @ 2024-03-26 15:17:51

@lunjiahao ohhhhhhhh！AC了！！！！！发现了两个最重要的错误

第一个是回文数判断的时候忘记循环了

第二个是

for(i=a;((i%2)!=0)&&i<=b;i++)

如果a是偶数直接没进入循环 i也不会++

非常非常感谢！！！

by Netherite_Pickaxe @ 2024-03-27 21:22:54

不是

大哥们

直接用题面上给的方法不行吗

code:

#include<bits/stdc++.h>
#define rep(i,m,n,f) for(int (i)=(m);(i)<=(n);(i)+=(f))
#define crep(i,m,n,f) for(int (i)=(m);(i)<=(n);(i)+=(f))
#define drep(i,m,n,f) for(int (i)=(m);(i)>=(n);(i)-=(f))
#define xrep(i,m,n,f) for(int (i)=(m-1);(i)<=(n-1);(i)+=(f))
#define zrep(i,m,n,f) for(int (i)=(m-1);(i)>=(n-1);(i)-=(f))
using namespace std;
bool ispr(int x)
{
    for(int i=2;i<=sqrt(x);i+=1)
    {
        if(x%i==0)
        return false;
    }
    return true;
}
inline void print(int c)
{
    printf("%d\n",c);
}
inline void setup()
{
    //SOURCE
    int a,b;
    cin>>a>>b;
    int ans;
    for(int d1=2;d1<=9;d1+=1)
    {
        ans=d1;
        if(ispr(ans)==true and ans>=a and ans<=b)
        print(ans);
    }
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            ans=100*d1+10*d2+d1;
            if(ispr(ans)==true and ans>=a and ans<=b)
            print(ans);
        }
    }
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            for(int d3=0;d3<=9;d3+=1) 
            {
                ans=10000*d1+1000*d2+100*d3+10*d2+d1;
                if(ispr(ans)==true and ans>=a and ans<=b)
                print(ans);
            }
        }
    }
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            for(int d3=0;d3<=9;d3+=1) 
            {
                for(int d4=0;d4<=9;d4+=1)
                {
                    ans=1000000*d1+100000*d2+10000*d3+1000*d4+100*d3+10*d2+d1;
                    if(ispr(ans)==true and ans>=a and ans<=b)
                    print(ans);
                }
            }
        }
    }
}
signed main()
{
    setup();
    exit(EXIT_SUCCESS);
}

by Netherite_Pickaxe @ 2024-03-27 21:24:32

等等

不小心发错了

code:


#include<bits/stdc++.h>
#define rep(i,m,n,f) for(int (i)=(m);(i)<=(n);(i)+=(f))
#define crep(i,m,n,f) for(int (i)=(m);(i)<=(n);(i)+=(f))
#define drep(i,m,n,f) for(int (i)=(m);(i)>=(n);(i)-=(f))
#define xrep(i,m,n,f) for(int (i)=(m-1);(i)<=(n-1);(i)+=(f))
#define zrep(i,m,n,f) for(int (i)=(m-1);(i)>=(n-1);(i)-=(f))
using namespace std;
bool ispr(int x)
{
    for(int i=2;i<=sqrt(x);i+=1)
    {
        if(x%i==0)
        return false;
    }
    return true;
}
inline void print(int c)
{
    printf("%d\n",c);
}
inline void setup()
{
    //SOURCE
    int a,b;
    cin>>a>>b;
    int ans;
    for(int d1=2;d1<=9;d1+=1)
    {
        ans=d1;
        if(ispr(ans)==true and ans>=a and ans<=b)
        print(ans);
    }
  if(11>=a and 11<=b)
   printf("11\n");
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            ans=100*d1+10*d2+d1;
            if(ispr(ans)==true and ans>=a and ans<=b)
            print(ans);
        }
    }
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            for(int d3=0;d3<=9;d3+=1) 
            {
                ans=10000*d1+1000*d2+100*d3+10*d2+d1;
                if(ispr(ans)==true and ans>=a and ans<=b)
                print(ans);
            }
        }
    }
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            for(int d3=0;d3<=9;d3+=1) 
            {
                for(int d4=0;d4<=9;d4+=1)
                {
                    ans=1000000*d1+100000*d2+10000*d3+1000*d4+100*d3+10*d2+d1;
                    if(ispr(ans)==true and ans>=a and ans<=b)
                    print(ans);
                }
            }
        }
    }
}
signed main()
{
    setup();
    exit(EXIT_SUCCESS);
}

by Netherite_Pickaxe @ 2024-03-27 21:27:50

#include<bits/stdc++.h>
#define rep(i,m,n,f) for(int (i)=(m);(i)<=(n);(i)+=(f))
#define crep(i,m,n,f) for(int (i)=(m);(i)<=(n);(i)+=(f))
#define drep(i,m,n,f) for(int (i)=(m);(i)>=(n);(i)-=(f))
#define xrep(i,m,n,f) for(int (i)=(m-1);(i)<=(n-1);(i)+=(f))
#define zrep(i,m,n,f) for(int (i)=(m-1);(i)>=(n-1);(i)-=(f))
using namespace std;
bool ispr(int x)
{
    rep(i,2,9,1)
    {
        if(x%i==0)
        return false;
    }
    return true;
}
inline void print(int c)
{
    printf("%d\n",c);
}
inline void setup()
{
    //SOURCE
    int a,b;
    cin>>a>>b;
    int ans;
    for(int d1=2;d1<=9;d1+=1)
    {
        ans=d1;
        if(ispr(ans)==true and ans>=a and ans<=b)
        print(ans);
    }
   if(11>=a and 11<=b)
   printf("11\n");
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            ans=100*d1+10*d2+d1;
            if(ispr(ans)==true and ans>=a and ans<=b)
            print(ans);
        }
    }
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            for(int d3=0;d3<=9;d3+=1) 
            {
                ans=10000*d1+1000*d2+100*d3+10*d2+d1;
                if(ispr(ans)==true and ans>=a and ans<=b)
                print(ans);
            }
        }
    }
    for(int d1=1;d1<=9;d1+=2) 
    {
        for(int d2=0;d2<=9;d2+=1) 
        {
            for(int d3=0;d3<=9;d3+=1) 
            {
                for(int d4=0;d4<=9;d4+=1)
                {
                    ans=1000000*d1+100000*d2+10000*d3+1000*d4+100*d3+10*d2+d1;
                    if(ispr(ans)==true and ans>=a and ans<=b)
                    print(ans);
                }
            }
        }
    }
}
signed main()
{
    setup();
    exit(EXIT_SUCCESS);
}

进化

by Netherite_Pickaxe @ 2024-03-27 21:29:38

Sorry

发错了