[오일러프로젝트] 41번문제

1부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다.
2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다.

n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?



가장 심플한 방식은 1 ~ 987654321까지  loop를 돌면서
소수인지 판정하는 것인데 이게 시간이 어마어마하게 걸린다...
그래서 일단 123은 제끼고 1234 ~ 123456789의 팬디지털 숫자를 모두 구한 후
이것을 소수인지 판별하며 가장 큰 것을 찾았음..

 

Python

	def isPrime(n):
	n = abs(int(n))
	if n < 2:
	return False
	if n == 2:
	return True
	if not n & 1:
	return False
	for x in range(3, int(n**0.5)+1, 2):
	if n % x == 0:
	return False
	return True
	# euler 24
	import itertools
	p=list()
	for n in range(2,11):
	l=list(range(1,n))
	permutations=list(itertools.permutations(l,len(l)))
	for t in permutations:
	s="".join(str(n) for n in t)
	p.append(s)
	p.sort()
	result = 0
	for n in p:
	if isPrime(n):
	if result < int(n):
	result = int(n)
	print (result)

view raw 41.py hosted with ❤ by GitHub

Ruby

	require 'mathn'
	def isPrime(n)
	return n.prime?
	end
	p=Array.new
	p = p + "123".split("").permutation.to_a
	p = p + "1234".split("").permutation.to_a
	p = p + "12345".split("").permutation.to_a
	p = p + "123456".split("").permutation.to_a
	p = p + "1234567".split("").permutation.to_a
	p = p + "12345678".split("").permutation.to_a
	p = p + "123456789".split("").permutation.to_a
	p.sort!
	result = 0
	p.each do |n|
	s=n.join("")
	if (isPrime(s.to_i))
	if result < s.to_i
	result = s.to_i
	end
	end
	end
	puts result

view raw 41.rb hosted with ❤ by GitHub

Perl

	use List::Permutor;
	use strict;
	use warnings;
	sub isPrime
	{
	my ($number) = @_;
	$number = abs $number;
	my $sqrt = sqrt $number;
	my $d = 2;
	while (1)
	{
	return 0 if ( $number % $d == 0 );
	return 1 if ( $d > $sqrt );
	$d++;
	}
	}
	our $result = 0;
	sub getPrime {
	my ($number) = @_;
	while (my @p = $number->next) {
	my $str = join "", @p;
	if (isPrime($str)) {
	if($result < $str) {
	$result = $str;
	}
	}
	}
	}
	my $perm = new List::Permutor qw /1 2 3 4/;
	&getPrime($perm);
	$perm = new List::Permutor qw /1 2 3 4 5/;
	&getPrime($perm);
	$perm = new List::Permutor qw /1 2 3 4 5 6/;
	&getPrime($perm);
	$perm = new List::Permutor qw /1 2 3 4 5 6 7/;
	&getPrime($perm);
	$perm = new List::Permutor qw /1 2 3 4 5 6 7 8/;
	&getPrime($perm);
	$perm = new List::Permutor qw /1 2 3 4 5 6 7 8 9/;
	&getPrime($perm);
	print "$result";

view raw 42.pl hosted with ❤ by GitHub

그런데 팬디지털 수를 만들어 List로 저장하는 로직들이 마음에 안든다.. 더 좋은 방법들이 있을 것 같은데...으..