脳log[20110208] Q50

最終更新: 2011-02-09T20:16+0900

♪ [ProjectEuler] Q50

 Q50

1. 100万未満の素数リストを作成。
2. リストをコピーして作業領域とする。
3. コピーしたリストの要素に、一つ右の位置の素数、二つ右の位置の素数、以下略を加えていき、都度、和が素数かどうか確かめる。

時間がかかるので逐一進捗を表示してる。この問題に魔法の一手なんてあるのかね。

primes = []
is_prime = lambda{|x|
	result = true
	primes.each{|prime|
		quotient, remainder = x.divmod(prime)
		if remainder == 0
			result = false
			break
		end
		break if quotient < prime
	}
	return result
}
2.upto(999_999){|x|
	primes.push x if is_prime.call x
}
puts "#{primes.size} primes under 1 million."

work = primes.dup
step = 0
primes_found = []
live_elements = work.size
while 0 < live_elements
	step += 1
	primes_found.clear
	live_elements = 0
	print "step #{step}\r"
	0.upto(work.size-1-step){|i|
		work[i] += primes[i+step]
		if work[i] < 1_000_000
			live_elements += 1
			primes_found.push work[i] if is_prime.call work[i]
		end
	}
	if primes_found.empty?
	elsif primes_found.size < 10
		puts "step #{step}: #{primes_found.join ' '}"
	else
		puts "step #{step}: #{primes_found.size} primes"
	end
end

魔法の一手はなくても……

• 素数列の作成と和の評価を同時進行にできるかも。
• 作業領域の範囲の狭め方が下手。
• 奇数ステップ(偶数個の素数の和)は不要。
• 100万に近い素数は不要。(それを一つ加えただけで 100万を超えるんでは項数を稼げない)
• 項数の上限は求められる。

答えを出した後でググるのが楽しい。フォーラムは読んでないけど、多分これ以上ないっていうような答えが書いてありそうで、面白くなさそうな気がしてる。(理解できない数学的知識が使われてたら、print XXXXXXX(answer); って書かれてるのと変わらないから)