c - 找到以 K 为底的第 n 个回文素数

问题描述

我最近问了一个关于查找一个数字是否以 K 为底的回文的问题，我得到了答案。我最近的问题

现在我有一个更复杂的问题，我们将得到两个数 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。

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

请注意，我不允许使用数组、向量和字符串，而且我不能使用 stdio.h 和 math.h 以外的库。这是我的程序，任何人都可以在其中找到任何问题：（我定义 intPow 是因为数学中的 pow 函数给出了一个浮点数，有时它会导致问题）

#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;


}

标签： calgorithmpalindrome

解决方案：将回文改为

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 的素数，并与谷歌上的已知值进行比较。在这种情况下，这有效
要测试回文，请从互联网上选择一个可行的解决方案（即使您无法提交使用数组/字符串的解决方案，您也可以使用它们进行测试！）。然后在某个基数中从 1 迭代到 10^7 并检查两个函数是否返回相同的值。
使用 base 3 进行测试，很快发现 56 没有给出相同的输出。不正确的是你的。
然后是修复你的功能的问题，你现在知道哪个是问题，甚至有一个例子说明它在哪里不起作用

c - 找到以 K 为底的第 n 个回文素数

问题描述

解决方案

推荐阅读