反质数

Question

我想检查一个数字 a 及其倒数是否为素数。该数字必须从键盘读取。

限制是：

1≤a≤2000000000
a没有最后一位0

以下是 a 和预期输出

的一些示例输入

Input  Output
5      Yes
112    No
17     Yes

这是我尝试过的：

#include <iostream>
using namespace std;

int main()
{
    int a;
    cin>>a;
    int RevNum =0;
    int Remain;
    int i=2;
    int prim = 1;
    int a_inainte = a;
    if ( (1 <= a && a <= 2000000000) && (a % 10 != 0) )
    {
            while(a != 0)
            {
                Remain = a % 10;
                RevNum = RevNum * 10 + Remain;
                a /= 10;
            }

            if (i < RevNum && i< a_inainte)
            {
                if (RevNum % i == 0 || a_inainte % i ==0)
                    prim = 0;
                ++i;
            }

            if (RevNum == 1 && a_inainte == 1)
                prim = 0;
            if (prim == 1)
                cout<<"DA";
            else
                cout<<"NU";
        }
        else
        {
            cout<<"NU";
        }
    return 0;
    }

我不确定为什么，但代码块中的所有内容似乎都没有问题，但我仍然没有在测试中得到所有分数（这是因为编译器检查带有更多数字的代码）。

Answer 1

您可以编写一个简短的函数来检查数字的素数。

我将以下代码基于 pseudocode code from Wikipedia。那里更深入地解释了这是如何工作的，但本质上要测试数字 n 是否为素数，您需要检查它是否可以被 [=17= 中的任何素数 i 整除] 到 sqrt(n).

bool is_prime(int n) {
    if (n <= 1)
        return false;
    else if (n <= 3)
        return true;
    else if (n % 2 == 0 || n % 3 == 0)
        return false;

    int i = 5;
    while (i*i <= n) {
         if (n % i == 0 || n % (i + 2) == 0)
             return false;
         i += 6;
    }
    return true;
}

现在你可以通过调用

来检查a是否是素数

is_prime(a);

要检查反转是否为素数，您需要计算 a 的反转。我发现了 Arslan7041 here 的一种有趣方法，它的工作原理与您已经在做的几乎相同：

int reverse(int x) {
    bool negative = false;
    if(x < 0) {
        negative = true;
        x = -x;
    }

    int reversed = 0;
    while(x > 0) {
        reversed = reversed*10 + x%10;
        x /= 10;
    }

    if(negative) reversed = -reversed;

    return reversed;
}

现在您可以检查 a 的倒数是否为素数：

 is_prime(reverse(a));

最后，我们可以用一个简单的 if 语句解决您的特殊两个限制。

if (1 <= a && a <= 2000000000 && a % 10 != 0 
    && is_prime(a) && is_prime(reverse(a)) ) {
    cout << "DA\n";
}

Answer 2

我假设您想通过除以小于或等于这些数字 a 的所有整数来验证 a 或 a 的倒数是否为素数，但在代码中您只除以 i = 2 和 i = 3 . 你必须遍历 i.

反质数

Reverse Prime Number

c++

numbers

calculation