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

from datetime import datetime
import math

def isPrime(x):
    if x < 2 : return False
    max = math.floor(math.sqrt(x))+1
    #print("==x=={}==MAX=={}".format(x,max))
    for n in range(2,max):
        if x % n == 0:
            return False
    else:
        return True
def primes(n = 2,max=3):
   while(n < max):
       if isPrime(n): yield n
       n += 1

def main():
    target = 600851475143
    maxPrimeFactor = 0
    for n in primes(2,int(math.sqrt(target))):
        if target % n == 0:
            maxPrimeFactor = n
    print(maxPrimeFactor)

if __name__ == "__main__":
    startTime = datetime.now()
    main()
    print(datetime.now()-startTime)
6857
0:00:11.178640

PHP İle Çözüm

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

function isPrime($n){
    if($n<2)
        return false;
    for($i=2; $i<=sqrt($n); $i++){
        if($n % $i == 0)
            return false;
    }
    return true;
}
$startTime = microtime_float();
$target = (float)600851475143;
$maxPrimeFactor =0;
for($n = 2; $n<=sqrt($target); $n++){
    if(bcmod($target, $n) == 0 && isPrime($n) ){
        $maxPrimeFactor = $n;
    }
}
echo $maxPrimeFactor."\n";
$executionTime = microtime_float()- $startTime;
echo "Execution Time: ".$executionTime;
6857
Execution Time: 17.632016897202

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