Builder

web application developer blog

Project Euler Problem 3: En büyük Asal Çarpan, PHP ve Python ile Çözüm

13195’in asal çarpanları: 5, 7, 13 ve 29.
600851475143 ‘ün en büyük asal çarpanı nedir?

Not: Sorunun çözümüne geçmeden önce asal sayıların bulunması ile ilgili bir bilgi paylaşmak isterim. Genellikle okullarda asal sayılı tespitinde bir sayının kendisinden küçük tüm sayılara bölünüp bölünemediğine bakılır.

Örneğin 17 saysının asal olup olmadığına bakmak için 1-16 arasındaki tüm sayılar denenir.

Oysaki, bir sayının çarpanları karşılıklıdır. Örneğin 12 sayısını ele alacak olursak: 12 sayısı 2 ‘ye tam bölündüğünde 6 çıkar ki bu durumda 6’ya da tam bölünebilir demek oluyor. Devamında 3 ile bölündüğünde 4 çıkar ki bu 4’de de tam olarak bölünebilir demek oluyor. Bu durumda 4 ve 6’yı test etmeye gerek yoktur. Test edilmesi gereken en büyük sayı √12 olmalıdır. Böylece kod en az iki kat daha hızlı çalışır.

Python İle Çözüm

PHP İle Çözüm

Not: PHP ile büyük sayıların mod alma işlemi % işleci(operatörü) ile yapılamamaktadır. Onun için BC Math eklentisini kullanmak gerekiyor. Detaylı bilgi için şuraya bakabilirsiniz:

http://php.net/manual/en/book.bc.php

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir