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

41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?

이거 결국은 풀지못하고
풀이를 찾아본문제... 소수배열 만들어 놓고 for 2개로 돌리면 되기는 하는데
100만이하의 소수면 거의 끝나지도 않을 것 같고...해서 외국 블로거의 풀이를
보고 이를 분석하는 것으로 만족...ㅋ

1~100까지의 예를들면
소수배열 : [2,3,5,7,11,13,17,19,23,29,31...]
각 소수의 합 : [2,5,10,17,28,41,58,77,100]

1) index ~ n까지의 합은 sum(n) - prime_list[index]와 같다.

index ~ n까지의 최고 term을 가진 소수를 찾았으니 그다음은 n ~ 찾으면 된다.

를 바탕으로한 로직임

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
	max = 100
	primes = [int(n) for n in range(2, max+1) if isPrime(n)]
	prime_sum = [0]
	sum = 0
	count = 0
	while (sum < max):
	sum+=primes[count]
	prime_sum.append(sum)
	count+=1
	print (prime_sum, count)
	terms = 1
	max_prime=0
	for i in range(count):
	for j in range(i+terms, count):
	n = prime_sum[j] - prime_sum[i]
	print ("i={0}, j={1}, terms={2}, max_prime={3}, n={4}, isPrime={5}, j-i={6}".format(i,j,terms,max_prime,n,isPrime(n),j-i > terms))
	if (j-i>terms and isPrime(n)):
	(terms,max_prime) = (j-i,n)
	print ("Answer to Problem 50 = ",max_prime," with ",terms," terms\n");

view raw 50.py hosted with ❤ by GitHub

Ruby

	require 'mathn'
	def isPrime(n)
	return n.prime?
	end
	max = 100
	primes = Array.new
	(2..100).each do |n|
	if isPrime(n)
	primes.push(n.to_i)
	end
	end
	primes_sum = Array.new(0)
	sum = 0
	count = 0
	while (sum < max)
	sum += primes[count]
	primes_sum.push(sum)
	count += 1
	end
	terms = 1
	max_prime = 0
	(0..count-1).each do |i|
	(i+terms..count-1).each do |j|
	n = primes_sum[j] - primes_sum[i]
	if (j-i > terms and isPrime(n))
	terms = j-i
	max_prime = n
	end
	end
	end
	puts max_prime

view raw 50.rb hosted with ❤ by GitHub

Perl

	use strict;
	use warnings;
	sub is_prime_number {
	my($num) = @_;
	my $t=2;
	while ($t <= $num) {
	my $rest = $num % $t;
	if ($rest==0 and $t==$num) {
	return 1;
	} elsif ($rest == 0 and $t != $num) {
	return 0;
	} else {
	$t+=1;
	}
	}
	0;
	}
	my $max = 100;
	my @primes;
	my @prime_sum;
	foreach my $n ((2..$max)) {
	if (is_prime_number($n)) {
	push @primes, $n;
	}
	}
	my $sum = 0;
	my $count = 0;
	while ($sum < $max) {
	$sum += $primes[$count];
	push @prime_sum, $sum;
	$count += 1;
	}
	my $terms = 1;
	my $max_prime = 0;
	foreach my $i (0..$count-1) {
	foreach my $j ($i+$terms..$count-1) {
	my $n = $prime_sum[$j] - $prime_sum[$i];
	if($j-$i > $terms and is_prime_number($n)) {
	$terms = $j-$i;
	$max_prime = $n;
	}
	}
	}
	print "$max_prime";

view raw 50.pl hosted with ❤ by GitHub