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

1부터 n까지의 각 숫자를 한번씩만 써서 만들 수 있는 숫자를 팬디지털(pandigital)이라고 합니다.
예를 들면 15234는 1부터 5의 숫자가 한번씩만 쓰였으므로 1 ~ 5 팬디지털입니다.

7254라는 숫자는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다.

이런 식으로 a × b = c 가 1 ~ 9 팬디지털이 되는 모든 c의 합은 얼마입니까?

(참고: 어떤 c는 두 개 이상의 (a, b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다)


일단 약수를 구한 후
0이 있는 것 제외, a,b,c 합친 길이가 9가 아닌 것 제외 하는 방식으로
brute-force. 다만 상한선을 100000으로 잡은 것은 어림짐작...

 

Python

	def getDivisors(n):
	divisors = []
	for i in range(1, int(n**0.5)+1):
	if n % i == 0:
	divisors += [int(i), int(n/i)]
	#divisors.remove(n)
	divisors.sort()
	#print("divisros : {0}".format(divisors))
	return sorted(list(set(divisors)))
	r=0
	for n in range(2, 100000):
	if '0' in str(n):
	continue
	l = getDivisors(n)
	end_offset=len(l)-1
	start_offset=0
	while (start_offset!=end_offset and start_offset <= end_offset):
	a=l[start_offset]
	b=l[end_offset]
	start_offset+=1
	end_offset-=1
	if '0' in str(a) or '0' in str(b):
	continue
	joined_n = str(a)+str(b)+str(n)
	if (len(joined_n) == 9):
	temp_l = ''.join(sorted([ c for c in joined_n]))
	if '123456789' in temp_l:
	print(a,b,n)
	r+=n
	break
	print ("result : {0}".format(r))

view raw 32.py hosted with ❤ by GitHub

Ruby

	require 'set'
	def getDivisors(num)
	divisors=Set.new
	l=Math.sqrt(num).to_i
	for i in (1..l+1)
	if num % i == 0
	divisors.add(i)
	divisors.add(num/i)
	end
	end
	#divisors.delete(num)
	divisors = divisors.to_a
	divisors.sort!
	return divisors
	end
	r=0
	(2..100000).each do |n|
	if n.to_s.include? "0"
	next
	end
	l = getDivisors(n)
	end_offset=l.length-1
	start_offset=0
	while (start_offset != end_offset and start_offset <= end_offset)
	a=l[start_offset]
	b=l[end_offset]
	start_offset+=1
	end_offset-=1
	if a.to_s.include? "0" or b.to_s.include? "0"
	next
	end
	joined_n = a.to_s + b.to_s + n.to_s
	temp_l = Array.new
	if(joined_n.length == 9)
	joined_n.each_char{|c| temp_l.push(c)}
	temp_l.sort!
	temp_s = temp_l.join
	if temp_s.include? "123456789"
	puts "#{a}, #{b}, #{n}"
	r+=n
	break
	end
	end
	end
	end
	puts r

view raw 32.rb hosted with ❤ by GitHub

Perl

	use strict;
	use warnings;
	use Math::Complex;
	sub getDivisors {
	my ($num) = @_;
	my %divisors_hash=(); #키가 약수
	my $l=sqrt($num)+1;
	foreach my $n ((1..$l)) {
	if ($num % $n == 0) {
	unless(exists ($divisors_hash{$num / $n})) {
	$divisors_hash{$num / $n}=1;
	}
	unless(exists ($divisors_hash{$n})) {
	$divisors_hash{$n}=1;
	}
	}
	}
	#print "num : $num, divisors : @{keys %divisors_hash} \n";
	my @divisors=();
	foreach my $key ( keys %divisors_hash ) {
	push @divisors, $key;
	}
	sort {$a <=> $b} @divisors;
	}
	my $r=0;
	foreach my $n ((2..100000)) {
	if ($n =~ m/0/) {
	next;
	}
	my @l = getDivisors($n);
	print "n : $n, @l \n";
	my $end_offset = @l - 1;
	my $start_offset = 0;
	while ($start_offset != $end_offset and $start_offset <= $end_offset) {
	my $a=$l[$start_offset];
	my $b=$l[$end_offset];
	$start_offset+=1;
	$end_offset-=1;
	if ($a =~ m/0/ or $b =~ m/0/) {
	next;
	}
	my $joined_n = $a.$b.$n;
	#print "joined_n : $joined_n";
	if (length $joined_n == 9) {
	my @temp_l = split //, $joined_n;
	@temp_l = sort @temp_l;
	my $temp_s = join("", @temp_l);
	if ($temp_s =~ m/123456789/) {
	$r+=$n;
	print "$a, $b, $n \n";
	last;
	}
	}
	}
	}
	print "$r \n";

view raw 32.pl hosted with ❤ by GitHub