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

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다.
또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다.
따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다.
두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?


문제 자체를 이해하지 못 해서 고생했다.
결국 28123미만의 양의 정수 중 초과수가 아닌 정수들의 합을 원하는 것인데
문제가 왜 저리...--;

28123미만의 양의 정수의 합을 구해놓고 그중 초과수의 합을 빼는 로직으로 구현

 

Python

	# xinuguru님의 function
	def getDivisors(N):
	divisors = []
	for i in range(1, int(N**0.5)+1):
	if N % i == 0:
	divisors += [i, N/i]
	divisors.remove(N)
	divisors.sort()
	if N==110:
	print("divisros : {0}".format(divisors))
	return sorted(list(set(divisors)))
	def isAbundant(N):
	divisors = getDivisors(N)
	total = sum(divisors)
	#if N < total:
	#print(N)
	#print("N : {0}, divsors : {1}".format(N, divisors))
	if N < total:
	return True
	else:
	return False
	limit = 28123
	abundantList = [n for n in range(12, limit) if isAbundant(n)]
	#print (abundantList)
	sumOfAbundant = set()
	for i in abundantList:
	for j in abundantList:
	if i+j < limit:
	sumOfAbundant.add(i+j)
	#a=sum(range(1,limit))
	#b=sum(sumOfAbundant)
	#print ("a : {0}, b : {1}".format(a,b))
	total = sum(range(1,limit)) - sum(sumOfAbundant)
	print(total)

view raw 23.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!
	if num==110
	puts "divisors : #{divisors}"
	end
	return divisors
	end
	def isAbundant(num)
	divisors = getDivisors(num)
	total = divisors.inject(:+)
	#puts "num : #{num}, total : #{total}"
	if num < total
	#puts num
	end
	if num < total
	return true
	else
	return false
	end
	end
	limit = 28123
	abundantList = (12..limit).to_a.select{|v| isAbundant(v)}
	#puts "list : #{abundantList}"
	sumOfAbundant = Set.new
	for i in abundantList
	for j in abundantList
	if i+j < limit
	sumOfAbundant.add(i+j)
	end
	end
	end
	#a=(1..limit-1).to_a.inject(:+)
	#b=sumOfAbundant.inject(:+)
	#puts "a : #{a}, b : #{b}"
	total = (1..limit-1).to_a.inject(:+) - sumOfAbundant.inject(:+)
	puts total

view raw 23.rb hosted with ❤ by GitHub

Perl

	use strict;
	use warnings;
	use Math::Complex;
	use List::Util qw (sum);
	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 ) {
	unless ($key == $num) {
	push @divisors, $key;
	}
	}
	print "num : $num, divisors : @divisors \n";
	return @divisors;
	}
	sub isAbundant {
	my ($num) = @_;
	my @divisors = getDivisors($num);
	my $total = sum @divisors;
	if ($total > $num) {
	#print "num : $num, total : $total \n";
	return 1;
	} else {
	return 0;
	}
	}
	my $limit = 28123;
	my @abundantList=();
	foreach (12..$limit-1) {
	if (isAbundant($_)) {
	push @abundantList, $_;
	}
	}
	#print "a : @abundantList";
	my %sumOfAbundant=();
	foreach my $i (@abundantList) {
	foreach my $j (@abundantList) {
	my $t=$i+$j;
	if ($t < $limit and (!exists ($sumOfAbundant{$t}))) {
	$sumOfAbundant{$t}=1;
	}
	}
	}
	#print "sum_of_abundant : @{keys %sumOfAbundant}";
	my $result = 0;
	foreach (keys %sumOfAbundant) {
	$result += $_;
	}
	$result = sum (1..$limit-1) - $result;
	print"total : $result";

view raw 23.pl hosted with ❤ by GitHub