后3个WA求助

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

145a @ 2024-02-29 17:04:07

#include<iostream>

#include<bitset>

#include<algorithm>

#include<vector>

using namespace std;

auto getPrimeList()

{

    const unsigned int maxNum = 10000000;

    bitset<maxNum> compositeTagList;

    vector<unsigned int> primeList = {};

    for (unsigned int i = 2; i < maxNum; i += 1)

    {

        if (compositeTagList[i] == false)

        {

        for (unsigned long int j = i * i; j < maxNum; j += i)

        {

            if (compositeTagList[j] == false)

                compositeTagList[j] = true;

        }

        primeList.push_back(i);

        }

    }

    return primeList;

}

auto primeList = getPrimeList();

auto isPalindrome(unsigned int x)

{

    if (x % 10 == 0 && x != 0) return false;

    unsigned int revertedNum = 0;

    while (x > revertedNum)

    {

        revertedNum = revertedNum * 10 + x % 10;

        x /= 10;

    }

    return x == revertedNum || x == revertedNum / 10;

}

int main()

{

    unsigned int a, b;

    cin >> a >> b;

    for (const unsigned int &x: primeList) {

        if(a <= x && x <= b && isPalindrome(x))

        {

            cout << x << endl;

        }

    }

    return 0;

}

by Louis_lxy @ 2024-02-29 18:15:51

你的素筛有问题吧,为什么从 i*i 开始筛呢,不应该是 2*i


by 145a @ 2024-02-29 21:09:32

@ldh270657080 非常感谢!!!


|