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: