如何在整数范围内找到向后素数？

Question

我正在尝试解决逆向质数问题。

问题如下：

Find all Backwards Read Primes between two positive given numbers (both inclusive), the second one being greater than the first one. The resulting array or the resulting string will be ordered following the natural order of the prime numbers.

例子

backwardsPrime(2, 100) => [13, 17, 31, 37, 71, 73, 79, 97] 
backwardsPrime(9900, 10000) => [9923, 9931, 9941, 9967]

我试过这样做：

public function backwardPrime()
{
    $start = 7000;
    $stop = 7100;

    $ans = [];

    while($start <= $stop)
    {
        if($start > 10)
        {
            if($start !== $this->reverse($start))
            {
                if($this->isPrime($start) && $this->isPrime($this->reverse($start)))
                {
                    array_push($ans, $start);
                }
            }
        }
        $start++;
    }
    return $ans;
}

public function reverse($num)
{
    $reverse = 0;
    while($num > 0)
    {
        $reverse = $reverse * 10;
        $reverse = $reverse + $num%10;
        $num = (int)($num/10);
    }
    return $reverse;
}

public function isPrime($num)
{
    if($num == 1 || $num == 2 || $num == 3)
        return true;
    elseif ($num%2 == 0 || $num%3 == 0)
        return false;
    else
    {
        $i=5;
        while($i<=$num/2)
        {
            if($num%$i===0)
            {
                return false;
            }
            $i++;
        }
    }
    return true;
}

我能够得到适当的答案，但是在单一函数中做同样的事情时我无法得到它：

public function backwardPrimes()
{
    $start = 7000;
    $stop = 7100;
    $ans = [];
    while($start <= $stop)
    {
        $isStartPrime = true;
        $isReversePrime = true;
        if($start > 10)
        {
            $reverse = 0;
            $num = $start;
            while($num > 0)
            {
                $reverse = $reverse * 10;
                $reverse = $reverse + $num%10;
                $num = (int)($num/10);
            }
            if($start !== $reverse)
            {
                if($start%2 != 0 && $start%3 != 0)
                {
                    $i =5;
                    while($i<=$start/2)
                    {
                        if($start%$i === 0)
                        {
                            $isStartPrime = false;
                            break;
                        }
                        $i++;
                    }
                }
                if($reverse%2 != 0 && $reverse%3 != 0)
                {
                    $i =5;
                    while($i<=$reverse/2)
                    {
                        if($reverse%$i === 0)
                        {
                            $isReversePrime = false;
                            break;
                        }
                        $i++;
                    }
                }
                if($isStartPrime && $isReversePrime)
                {
                    array_push($ans, $start);
                }
            }
        }
        $start++;
    }
    return $ans;
}

不知道哪里错了，指导一下。

谢谢。

Answer 1

一个 emirp（"prime" 向后拼写）是一个素数，其（以 10 为底）反转也是素数，但它不是回文素数。换一种说法 Backwards Read Primes 是当以 10 为底（从右到左）向后读取时是不同素数的素数。（这排除了回文素数。）

试试这个简短的解决方案，我在其中使用了两个辅助函数 reverse 和 isPrime :

isPrime：感谢@Jeff Clayton 测试素数的方法，更多信息请点击
reverse：使用php函数[strrev()][1]，这个方法将一个字符串取反，我们将使用这个技巧通过转换来反转一个数字将其转换为字符串并将其反转并转换回整数。
backwardsPrime：最后一个函数的工作是遍历从 $min 值到 $max 值的数字范围，并测试该数字是否为质数及其反面是否也是质数，并且它是如果所有这些条件都为真，则不是回文数，然后我们将其添加到结果数组中。

实施

function isPrime($number) 
{
  return !preg_match('/^1?$|^(11+?)+$/x', str_repeat('1', $number));
}

function reverse($n) 
{
    return (int) strrev((string) $n);
}

function backwardsPrime($min, $max)
{
    $result = [];

    foreach(range($min, $max) as $number) {
        $reverse = reverse($number);
        if($reverse !== $number  && isPrime($number) && isPrime($reverse)) {    
           $result[] = $number;
        }
    }

    return $result;
}

echo "<pre>";          
print_r(backwardsPrime(2, 100));
print_r(backwardsPrime(9900, 10000));

输出：

Array
(
    [0] => 13
    [1] => 17
    [2] => 31
    [3] => 37
    [4] => 71
    [5] => 73
    [6] => 79
    [7] => 97
)



   Array
(
    [0] => 9923
    [1] => 9931
    [2] => 9941
    [3] => 9967
)

您甚至可以像这样优化 backwardsPrime 函数：

function backwardsPrime($min, $max)
{
    $result = [];

    foreach(range($min, $max) as $number) {
        $reverse = reverse($number);
        if($reverse !== $number && !in_array($number, $result) && isPrime($number) && isPrime($reverse)) {  
           $result[] = $number;
        }
    }

    return $result;
}

如何在整数范围内找到向后素数？

How to find backward primes within a range of integers?

php

primes

function

range

palindrome

实施