欧拉计划35题：100万以上有多少个循环质数？附模块 Math-Prime-Util的使用：17秒的差距：思考总能学习新的东西，思考总能得到好的结果

欧拉计划35题：100万以下有多少个循环质数？附模块 Math-Prime-Util的使用：17秒的差距：：思考总能学习新的东西，思考总能得到好的结果

这里程序其实还有很多的问题，首先，求100000以内的素数有一个专门的模块，明天好好研究一下，再做总结，

其次，循环数的遍历一块，很啰嗦，但是还没有找到更好的方法，这个也需要优化。

我们称197为一个循环质数，因为它的所有轮转形式: 197, 971和719都是质数。

100以下有13个这样的质数: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97.

100万以下有多少个循环质数？

程序如下：

my $start_time=time;
my %hash;
my $i;
my $flag;

#**************************************************#
#************以下获取100万以下的质数库*************#
for($i=11;$i<1000000;$i+=2)
{
	if($i%3==0)
	{
		next;
	}
	else
	{
		$flag=0;
		foreach(2..$i**0.5+1)
		{
			if($i%$_==0)
			{
				$flag=1;
				last;
			}
			else
			{
				next;
			}
		}
		if($flag==0)
		{
			$hash{$i}=$i;
		}
	}
}
#*************************************************#
use Algorithm::FastPermute('permute');

my $array;
my $all;
my @all;
my @array=  keys %hash;
my $cout=4;
foreach $array(@array)
{
	my @separt=split//,$array;
	$all[0]=$array;
	$all[1]=join "",$separt[1],$separt[2],$separt[3],$separt[4],$separt[5],$separt[0];
	$all[2]=join "",$separt[2],$separt[3],$separt[4],$separt[5],$separt[0],$separt[1];
	$all[3]=join "",$separt[3],$separt[4],$separt[5],$separt[0],$separt[1],$separt[2];
	$all[4]=join "",$separt[4],$separt[5],$separt[0],$separt[1],$separt[2],$separt[3];
	$all[5]=join "",$separt[5],$separt[0],$separt[1],$separt[2],$separt[3],$separt[4];
	$flag=0;
	foreach $all(@all)
	{
		if(exists$hash{$all})
		{
			next;
		}
		else
		{
			$flag=1;
			last;
		}
	}
	if($flag==0)
	{
		$cout=$cout+1;
	}
	else
	{
		next;
	}
}
print "$cout\n";
my $long=time-$start_time;
print "$long\n";

结果如下：

用时18s

C:\WINDOWS\system32\cmd.exe /c perl "C:\Documents and Settings\Administrator\桌
面\b.pl"
55
18
Hit any key to close this window...

然后我们修改程序，我们把获取素数的部分进行替换：

程序如下：

my $start_time=time;
use Math::Prime::Util ':all';
my $hash;
my @primes=@{primes(1000000)};
foreach $primes(@primes)
{
	$hash{$primes}=$primes;
}

use Algorithm::FastPermute('permute');

my $array;
my $all;
my @all;
my @array=  keys %hash;
my $cout=0;
foreach $array(@array)
{
	my @separt=split//,$array;
	$all[0]=$array;
	$all[1]=join "",$separt[1],$separt[2],$separt[3],$separt[4],$separt[5],$separt[0];
	$all[2]=join "",$separt[2],$separt[3],$separt[4],$separt[5],$separt[0],$separt[1];
	$all[3]=join "",$separt[3],$separt[4],$separt[5],$separt[0],$separt[1],$separt[2];
	$all[4]=join "",$separt[4],$separt[5],$separt[0],$separt[1],$separt[2],$separt[3];
	$all[5]=join "",$separt[5],$separt[0],$separt[1],$separt[2],$separt[3],$separt[4];
	$flag=0;
	foreach $all(@all)
	{
		if(exists$hash{$all})
		{
			next;
		}
		else
		{
			$flag=1;
			last;
		}
	}
	if($flag==0)
	{
		$cout=$cout+1;
	}
	else
	{
		next;
	}
}
print "$cout\n";
my $long=time-$start_time;
print "$long\n";

结果就只用了1秒钟

C:\WINDOWS\system32\cmd.exe /c perl "C:\Documents and Settings\Administrator\桌
面\c.pl"
55
1
Hit any key to close this window...