c - 查找基数 K 中的第 n 个回文素数

Question

我最近问了一个关于查找一个数字是否是基数 K 的回文数的问题，我得到了答案。 My Recent Question

现在我有一个更复杂的问题，我们将得到两个数字 n 和 k，并且我们必须找到基 K 中回文的第 n 个质数。

例如，如果我们得到 8 和 10，我们有 2 3 5 7 11 101 131 151，它们是回文和质数，所以答案是 151。另一个例子是 4 2，我们分别有 3 5 7 17 11 101 111 10001以 2 为基数，它们是质数和回文数，所以答案是 17。

n 和 k 的给出使得答案最多为 1E7。

我在法官系统中提交了我的程序，在某些情况下它给出了错误的答案，并且在一种情况下给出了时间限制错误。我不知道我的算法哪一部分是错误的，哪一部分没有优化。

请注意，我不允许使用数组、 vector 和字符串，而且我不能使用超过 stdio.h 和 math.h 的库。这是我的程序，任何人都可以发现其中的任何问题吗:(我定义了 intPow，因为数学中的 pow 函数给出了一个 float ，有时它会导致问题)

#include <stdio.h>
#include <math.h>
int primeCheck ( int n);
int palindrome ( int n,int base);
int digitCountBase (int n , int base);
int intPow (int a , int b);
int main()
{
    int n;
    int base;
    scanf("%d %d",&n,&base);
    int counter = 0;
    int i =2;
    int firstRound =1;
    while (counter!=n)
    {

        if (primeCheck(i))
        {
            if (palindrome (i,base))
            {
                counter++;
            }
        }
        if (counter ==n)
        {
            break;
        }
        if (firstRound)
        {
            i++;
            firstRound=0;
        }
        else{i+=2;}

    }
    printf("%d",i);
    return 0;
}
int primeCheck ( int n)
{
    if (n<2)
    {
        return 0;
    }
    if (n==4)
    {
        return 0;
    }
    else if (n<=5)
    {
        return 1;
    }

    if (n%2 ==0 || n%3 ==0 || n% 5 ==0)
    {

        return 0;
    }
     int i =5;
     int limit = sqrt(n)+2;
    for (int i =5;i<=limit;i+=6)
    {
        if (n%i==0||n%(i+2)==0)
        {
            return 0;
        }
    }
    return 1;
}

int palindrome ( int n,int base)
{
    int isTrue = 1;
    int digitCount = digitCountBase(n,base);

    int power = intPow(base,digitCount-1);
    while (n>0&& digitCount >0)
    {

        if (n%base != (n/power)&&digitCount!=1)
        {
            isTrue =0;
            return 0;

        }
        n = n- power;
        n=n/base;
        power = power /base;
        power = power /base;
        digitCount=digitCount-2;
    }

    return isTrue;

}
int digitCountBase (int n , int base)
{
    int digits=0;
    while (n)
    {
        digits++;
        n = n / base;
    }
return digits;

}

int intPow (int a , int b)
{
    int result = 1;
    for (int i=1;i<=b;i++)
    {
        result = result * a;
    }
    return result;


}

Answer 1

解决方案:将回文改为

int palindrome ( int n,int base)
    {
        int isTrue = 1;
        int digitCount = digitCountBase(n,base);
        int power = intPow(base,digitCount-1);

        int original = n;
        while (n>0&& digitCount >0)
        {

            if (n%base != (original/power) % base &&digitCount!=1)
            {
                isTrue =0;
                return 0;

            }
            n=n/base;
            power = power /base;
            digitCount=digitCount-2;
        }

        return isTrue;

    }

我是如何发现错误的:

• 您只做了两件事，素性测试和回文测试，因此检查这些是否正常工作是有意义的。
• 素数测试很简单，计算从 1 到 10^7 的素数，并与 Google 上的已知值进行比较。在这种情况下，这是可行的
• 要测试回文，请从互联网上选择一个可行的解决方案(即使您无法提交使用数组/字符串的解决方案，您也可以使用它们进行测试!)。然后在某个基数中从 1 迭代到 10^7 并检查两个函数返回的值是否相同。
• 使用基数 3 进行测试，很快发现 56 没有给出相同的输出。而错误的是你的。
• 然后就是修复你的函数，你现在知道哪个函数出了问题，甚至还有一个例子说明它在哪里不起作用