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

오일러는 다음과 같은 멋진 2차식을 제시했습니다.

n² + n + 41

이 식의 n에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다.
하지만 n = 40일 때의 값 40² + 40 + 41 은 40×(40 + 1) + 41 이므로 41로 나누어지고, n = 41일 때 역시 41² + 41 + 41 이므로 소수가 아닙니다.

컴퓨터의 발전에 힘입어 n² − 79n + 1601 이라는 엄청난 2차식이 발견되었는데, 이것은 n이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다.

아래와 같은 모양의 2차식이 있다고 가정했을 때,

n² + an + b   (단 | a | < 1000, | b | < 1000)

0부터 시작하는 연속된 n에 대해 가장 많은 소수를 만들어내는 2차식을 찾아서, 그 계수 a와 b의 곱을 구하세요.


위 식을 사용하면
b가 소수, a+b+1이 소수여야 한다는 사실을 알 수 있다.
이를 활용하여 brute-force..

 

Python

	def isPrime(n):
	# http://www.daniweb.com/software-development/python/code/216880
	'''check if integer n is a prime'''
	# make sure n is a positive integer
	n = abs(int(n))
	# 0 and 1 are not primes
	if n < 2:
	return False
	# 2 is the only even prime number
	if n == 2:
	return True
	# all other even numbers are not primes
	if not n & 1:
	return False
	# range starts with 3 and only needs to go up the squareroot of n
	# for all odd numbers
	for x in range(3, int(n**0.5)+1, 2):
	if n % x == 0:
	return False
	return True
	def getResult(a,b,n):
	r = n**2 + (a*n) + b
	return r
	max_n = 0
	max_a = 0
	max_b = 0
	for a in range(-999, 1000):
	for b in range(-999, 1000):
	n = 0
	while True:
	if isPrime(a+b+1) and isPrime(b):
	r = getResult(a,b,n)
	if isPrime(r):
	n+=1
	else:
	break
	else:
	break
	if n > max_n:
	print ("a : {0}, b : {1}, n : {2}".format(a,b,n))
	max_n = n
	max_a = a
	max_b = b
	print (max_a * max_b)

view raw 27.py hosted with ❤ by GitHub

Ruby

	require 'mathn'
	def isPrime(n)
	return n.prime?
	end
	def getResult(a,b,n)
	r = n**2 + (a*n) + b
	return r
	end
	max_n = 0
	max_a = 0
	max_b = 0
	(-999..999).each do
	|a|
	(-999..999).each do
	|b|
	n = 0
	while (true)
	if (isPrime(a+b+1) and isPrime(b))
	r = getResult(a,b,n)
	if (isPrime(r))
	n+=1
	else
	break
	end
	else
	break
	end
	end
	if (n > max_n)
	puts "a : #{a}, b : #{b}, n : #{n}"
	max_n = n
	max_a = a
	max_b = b
	end
	end
	end
	puts max_a*max_b

view raw 27.rb hosted with ❤ by GitHub

Allen님의 풀이와 코드.

n=0일 때를 고려하면, b는 1~1000구간의 소수여야함. b=2라면 n=2에서 전체가 2의 배수가 되므로 b != 2 b가2가아닌 소수라면 홀수이고, n=1에서 a가 홀수여야 전체가 홀수가 됨 따라서, 홀수인 a만 찾아보면 됨.

	require 'mathn'
	def prime_count(a,b)
	n = 0
	n += 1 while (n*n + a*n + b).prime?
	n
	end
	max,ma,mb = 1,nil,nil
	Prime.each(1000) do |b|
	(-999..999).step(2) do |a|
	max,ma,mb = prime_count(a,b),a,b if prime_count(a,b) > max
	end
	end
	puts ma*mb

view raw 27_2.rb hosted with ❤ by GitHub

Perl

	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++;
	}
	}
	my $max_a = 0;
	my $max_n = 0;
	my $max_b = 0;
	foreach my $a ((-999..999)) {
	foreach my $b ((-999..999)) {
	my $n = 0;
	while(1) {
	my $r = ($n**2) + ($n*$a) + $b;
	if(isPrime($r)) {
	$n+=1;
	} else {
	last;
	}
	}
	if( $n > $max_n) {
	print "a : $a, b : $b, n : $n \n";
	$max_n = $n;
	$max_a = $a;
	$max_b = $b;
	}
	}
	}
	print "{($max_a*$max_b)}";

view raw 27.pl hosted with ❤ by GitHub