脳log[20110206] Q46, Q47

最終更新: 2011-02-07T05:28+0900

♪ [ProjectEuler] Q46, Q47

 Q46

squares[]はソート済みなのに .include?()でそれを活かせないのが不満。

primes = [] # Omit 2. Even prime is not needed.
squares = [1]
def prime?(n)
	return false if 0 == n%2
	3.step(n/2, 2) {|x|
		return false if 0 == n%x
	}
	return true
end

x = 1
loop {
	x += 2
	squares.push((squares.size+1)**2) if squares.last < x
	if prime?(x)
		primes.push x
		next
	end
	print "#{x}\r"
	next if primes.any?{|prime| prime < x and squares.include?((x-prime)/2) }
	p x # answer
	break
}

 Q47

何の工夫もないのですんごく時間がかかる。

def prime_gt2?(n)
	return false if 0 == n%2
	x, upper_bound = 3, n/2
	while x <= upper_bound
		upper_bound, remainder = n.divmod(x)
		return false if 0 == remainder
		x += 1
	end
	return true
end

primes = [2]
have4primefactors = []
have4primefactor = lambda{|x|
	num_of_factors = 0
	primes.each{|prime|
		if x % prime == 0
			num_of_factors += 1
			break if 4 < num_of_factors
			x /= prime while x % prime == 0
		end
	}
	return num_of_factors == 4
}

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