Project Euler #53

Birilerinin Project Euler sorularının cevaplarını yayınladığını öğrendiğimde öfkelenmiştim. Ben adım adım çözerek yükselirken birileri siteye girip “çat çat” cevapları vererek listede yükselebiliyordu. Sonra düşündüm ki, bana ne? Project Euler insanın kendini geliştirebilmesi ve zaman geçirebilmesi için yaratılmış bir site. Ben aşağıda #53’ün cevabını yazacağım. Yani şimdiden bir spoiler ibaresi koyuyorum. 🙂 İstemeyen bakmaz.

Soru #53, bizden 1<= n <= 100 aralığında kaç tane C(n,r)’nin 1 milyondan yukarda olduğunu soruyor. Distinct value bulmaya gerek yok, basit bir brute force ile sonuca gidilebilir. Kombinasyon hesaplama işi bilgisayarı uzun süre meşgul edebiliyor, çünkü kombinasyon belli sayıların faktöriyellerine bakılarak bulunuyor:

C(n,r) = n! / r!(n-r)!

O nedenle gerektiği yerde bu faktöriyel sonuçlarını cachelemeye karar verdim. Sonuç olarak, aşağıdaki kodla çift çekirdekli 2.4 GHz makinede 0.15 saniyelik bir runtime ile cevaba ulaştım. Project Euler’de diğer cevaplara baktığımda daha verimli algoritmalara da ulaştım, bazıları Pascal Triangle kullanmış – ki bence mükemmel bir fikir. Ama benim algoritmam da hızlı bir şekilde sonuca ulaştırdı.

import sys
import math
import time
 
## author: Ekin Ocalan
## date: Mar 14, 2013
## project euler #53
 
fact_results = []
 
def fact(i):
	if i == 1:
		return i
	elif i &lt; 1:
 		return 1
 	else: 		return i * fact(i-1) 
 
def comb( i, j):
 	global fact_results
 	if fact_results[i] == 0:
 		fact_results[i] = fact(i)
 	if fact_results[j] == 0:
 		fact_results[j] = fact(j)
 	if fact_results[i-j] == 0:
 		fact_results[i-j] = fact(i-j) 	return fact_results[i] / (fact_results[j] * fact_results[i-j]) 
 
def main():
 	global fact_results
 	count = 0
 	for i in range(101):
 		fact_results.append(0)
 	for i in range(23,101):
 		for j in range(1,i+1):
 			if comb( i, j) &gt; 1000000:
				count += 1
				print 'found one on %d.C.%d' % (i,j)
 
	print 'finished. total: %d' % (count)
 
if __name__ == '__main__':
	start_time = time.time()
	main()
	print time.time() - start_time, "seconds"

Project Euler ve Asal Sayılar

Asal sayılara karşı tuhaf bir ilgim var. Otomattan yiyecek ya da içeçek seçerken dahi asal sayıdan seçmeye nedense özen gösteriyorum, hoşuma gidiyor.

Project Euler ise projecteuler.net adresinde yer alan, matematik ve kodlama egzersizi yapabileceğiniz hoş bir web sitesi. Şu anda 417 adet farklı probleme ev sahipliği yapmasının yanında her hafta yeni bir problem de ekleniyor. Zamanında ilk 50 problemi çözmüş ve bırakmıştım. O zamandan beri aklımın bir köşesinde hep dönüp problemlerin tümünü bitirmek vardı. Geçen haftalar içerisinde ise bu amacıma ulaşmak için problemleri çözmeye devam etmeye başladım.

Gelelim Project Euler ile asal sayılar arasındaki ilişkiye ve bu yazının asıl konusuna. Project Euler’de çözdüğüm birçok problemin içinde asal sayıların bir şekilde kullanımı mevcut. Problemler, çözen kişiyi time and space‘de optimizasyona yönelttiği için (milyonlar ve hatta milyarlara ulaşan sayıları bazen tek tek kontrol etmeniz gerekebiliyor) kullandığınız dilin de, algoritmanın da önemi büyüyebiliyor. Algoritmaya fazla önem vermeden problemleri çözen kişilerin genel olarak dil tercihi Assembly bile olabiliyor – ki bu bana düşünülmeden yazılmış kodlara yol açtığı için inanılmaz saçma geliyor. High-level bir programlama dili ile yazılmış, iyi tasarlanmış bir algoritmayla, Project Euler’in kendisinin de söylediği gibi soruları 1 dakikanın altında bir sürede çözmek neredeyse kesin. Problemler bu bağlamda tasarlanıyor.

Çözdüğüm ilk 50 soruda kullandığım asal sayı algoritmalarının (bir sayı asal mı değil mi) hiç de verimli olmadığını, problemleri çözmeye devam etmeye başladığım birkaç hafta öncesinde fark ettim. True ya da False döndüren küçük isPrime fonksiyonumun içinde sayıyı 2 ile kendisi arasında bir döngüye alıp kontrol ediyordum. Oysa ki buna gerek yokmuş; 2 ile sayının (bu sayıya x diyelim) karekökü arasında döngüye almak yeterli oluyor. Bunun sebebi de eğer x’in karekök(x)’ten büyük bir böleni (q diyelim) varsa (x=q*p), p sayısı karekök(x)’ten küçük oluyor. Böylece kontrol edilmesi mecburi olan sayılar azalıyor. Aşağıda örnek bir Python kodu var:

import math
 
## author: Ekin Ocalan
## date: Feb 3, 2013
## project euler #51
 
def is_prime(n):
	for i in xrange( 2, int(math.floor(math.sqrt(n)))):
		if n%i==0:
			return False
	return True