脳log[20110207] Q47, Q48, Q49

最終更新: 2011-02-09T01:05+0900

♪ [ProjectEuler] Q47, Q48, Q49

 Q47

昨日よりちょっとはマシになったかと。アホすぎた素数判定を、素因数の数を数える処理と一体化した。でも 10秒以上かかります。

primes = [2]
have4primefactors = []

num_of_factors = lambda{|x|
	prime_factors = 0
	primes.each{|prime|
		quotient, remainder = x.divmod(prime)
		if quotient < prime
			prime_factors += 1
			break
		end
		if remainder == 0
			prime_factors += 1
			break if 4 < prime_factors
			x /= prime while x % prime == 0
			break if x == 1
		end
	}
	return prime_factors
}

x = 2
loop {
	x += 1
	print "#{x}\r"
	case num_of_factors.call(x)
	when 1
		primes.push x
		have4primefactors.clear
	when 4
		have4primefactors.push x
		p have4primefactors.first if have4primefactors.length == 4
	else
		have4primefactors.clear
	end
}

 Q48

恥ずかしいほどまっすぐで乱暴なスクリプトだけど、コンソールの表示も待てないくらいノーウェイトで答えが出るんだから仕方がない。

p (1..1000).inject(0){|sum,x| sum + x**x }

 Q49

1. 4桁の素数リストを作る
2. リストから条件を満たす二つの素数を選ぶ
3. 計算で求めた三番目の数(三つのうち一番大きい)が条件を満たすか調べる。

10秒くらいかかります。

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(9999){|x|
	primes.push x if is_prime.call x
}

primes_4digit = primes.last(primes.length - primes.rindex{|x| x < 1000 } - 1)
0.upto(primes_4digit.size-1){|i|
	p = primes_4digit[i]
#	next if p == 1487
	(i+1).upto(primes_4digit.size-1){|j|
		q = primes_4digit[j]
		r = q + q - p
		next if p.to_s.split(//).sort != q.to_s.split(//).sort or
		        q.to_s.split(//).sort != r.to_s.split(//).sort
		k = nil
		(j+1).upto(primes_4digit.size-1){|_k|
			if r == primes_4digit[_k]
				k = _k
				break
			elsif r < primes_4digit[_k]
				break
			end
		}
		if k
			puts "#{p} #{q} #{r}"
#			exit
		end
	}
}