1

我正在做Project Euler问题。我目前正在研究圆形素数问题

数字 197 被称为圆素数，因为数字的所有旋转：197、971 和 719 本身都是素数。

100 以下的素数有 13 个：2、3、5、7、11、13、17、31、37、71、73、79 和 97。

一百万以下有多少个圆素数？

虽然检查某个东西是否是素数对我来说很容易，但我无法弄清楚如何获得数字的所有排列。经过大量搜索有关算法的提示后，我遇到了一个网站，该网站提供了 Java 代码，我在下面适应了 PHP。但是，在继续解决问题之前，我真的很想了解代码的不同位到底在做什么，尤其是在 for 循环中。到目前为止我对它的理解是，在for循环中，它以一个空前缀开始，然后循环遍历字符串并将字符串中的单个元素添加到前缀中，直到原始字符串中只剩下一个元素，在这一点上，它呼应了它。我是否正确理解这一点？如果没有，我错过了什么？

<?php
    getallcombos("","1234");
    function getallcombos($prefix,$string){
        if(strlen($string)==1){
            echo $prefix.$string."<br>";
        }
        $array=str_split($string);
        for($i=0;$i<strlen($string);$i++){
            $newstr=substr($string,0,$i).substr($string,$i+1);
            getallcombos($prefix.$array[$i],$newstr);
        }                       
    }       
?>
4

2 回答 2

3

问题不要求排列，而是要求旋转。这是不同的。对于所有旋转，您可以执行循环：

var number = "2031";
var rotations = [];
for (i = 0; i < number.length; ++i) {
    number = number.substring(1)
           + number[0];
    rotations.push(number);
}
console.log(rotations);

http://jsfiddle.net/T6Mur/

更新

特别为你：

function allRotArePrime(number) {
    var int;
    for (i = 0; i < number.length; ++i) {
        int = parseInt(
            number.substring(i) +
            number.substring(0, i)
        );
        // if (!isPrime(int)) return false;
        console.log(int);
    }
    //return true;
}

var num = 1927;
allRotArePrime(num.toString());

http://jsfiddle.net/T6Mur/3/

于 2013-10-15T14:26:56.143 回答
0

这if是你的停止条件。如果string只有长度 1 你只有一个排列。

for 循环很复杂，但它执行以下操作：

"" "1234"-> 循环 4 次，给出：

"1", "234"
"2", "134"
"3", "124"
"4", "123"

基本上，它将一个字符从 移动string到prefix，并进行所有组合以获得所有排列。

然后它运行然后下一个循环，它给出：

"12" "34"
"13" "24"
"14" "23"
"21" "34"
.. etc

最终你会得到：

"123" "4" -> "1234"
"124" "3" -> "1243"
.. etc

至于你的问题：请注意，对于像777它只会给你7776 次这样的数字来说，它是低效的。此外，您需要旋转，而不是排列。197应该给予197,971,719但不给予179,791,917

于 2013-10-15T14:24:12.753 回答