#3#4#5#7#8#9TLE?

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

MuYuMC @ 2024-05-03 19:01:30

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
int A[1000000];
int su(int x)
{
    int i,cnt = 1;
    if(x == 1) return 0;
    if(x == 2) return 0;
    for(i = 2;i < x;i++)
    {
        if(x % i == 0)
        {
            cnt = 0;
        }
    }
    return cnt;
}
int main()
{
    int n,m,i,w1,w2,w3,w4,w5,w6,w7,w8,w9,sum,j;
    cin >> n >> m;
    for(i = n;i <= m;i++)
    {
        if(i / 100000000 >= 1)
        {
            w1 = i % 10;
            w2 = i % 100 / 10;
            w3 = i % 1000 / 100;
            w4 = i % 10000 / 1000;
            w5 = i % 100000 / 10000;
            w6 = i % 1000000 / 100000;
            w7 = i % 10000000 / 1000000;
            w8 = i % 100000000 / 10000000;
            w9 = i % 1000000000 / 100000000;
            sum = w1 * 100000000 + w2 * 10000000 + w3 * 1000000 + w4 * 100000 + w5 * 10000 + w6 * 1000 + w7 * 100 + w8 * 10 + w9;
        }
        else{
            if(i / 10000000 >= 1)
            {
                w1 = i % 10;
                        w2 = i % 100 / 10;
                        w3 = i % 1000 / 100;
                        w4 = i % 10000 / 1000;
                        w5 = i % 100000 / 10000;
                        w6 = i % 1000000 / 100000;
                        w7 = i % 10000000 / 1000000;
                        w8 = i % 100000000 / 10000000;
                        sum = w1 * 10000000 + w2 * 1000000 + w3 * 100000 + w4 * 10000 + w5 * 1000 + w6 * 100 + w7 * 10 + w8;
            }
            else
            {
                if(i / 1000000 >= 1)
                {
                    w1 = i % 10;
                    w2 = i % 100 / 10;
                    w3 = i % 1000 / 100;
                    w4 = i % 10000 / 1000;
                    w5 = i % 100000 / 10000;
                    w6 = i % 1000000 / 100000;
                    w7 = i % 10000000 / 1000000;
                    sum = w1 * 1000000 + w2 * 100000 + w3 * 10000 + w4 * 1000 + w5 * 100 + w6 * 10 + w7;
                }
                else{
                    if(i / 100000 >= 1)
                    {
                        w1 = i % 10;
                        w2 = i % 100 / 10;
                        w3 = i % 1000 / 100;
                        w4 = i % 10000 / 1000;
                        w5 = i % 100000 / 10000;
                        w6 = i % 1000000 / 100000;
                        sum = w1 * 100000 + w2 * 10000 + w3 * 1000 + w4 * 100 + w5 * 10 + w6;
                    }
                    else{
                        if(i / 10000 >= 1)
                        {
                            w1 = i % 10;
                            w2 = i % 100 / 10;
                            w3 = i % 1000 / 100;
                            w4 = i % 10000 / 1000;
                            w5 = i % 100000 / 10000;
                            sum = w1 * 10000 + w2 * 1000 + w3 * 100 + w4 * 10 + w5;
                        }
                        else{
                            if(i / 1000 >= 1)
                            {
                                w1 = i % 10;
                                w2 = i % 100 / 10;
                                w3 = i % 1000 / 100;
                                w4 = i % 10000 / 1000;
                                sum = w1 * 1000 + w2 * 100 + w3 * 10 + w4;
                            }
                            else{
                                if(i / 100 >= 1)
                                {
                                    w1 = i % 10;
                                    w2 = i % 100 / 10;
                                    w3 = i % 1000 / 100;
                                    sum = w1 * 100 + w2 * 10 + w3;
                                }
                                else{
                                    if(i / 10 >= 1)
                                    {
                                        w1 = i % 10;
                                        w2 = i % 100 / 10;
                                        sum = w1 * 10 + w2;
                                    }
                                    else{
                                        sum = i;
                                    }
                                }
                            }
                        }

                    }
                }
            }
        }
        if(sum == i)
        {
            if(su(sum) == 1)
            {
                cout << sum << endl;
            }
        }
    }
    return 0;
}

by juruolaidayang_AKIOI @ 2024-05-03 19:16:40

10^8肯定炸呀,你外层是o(n)的,内层是近似o(n)的


|