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"

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

然后它运行然后下一个循环,它给出:

"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 回答