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

Leave a Reply