Euler Problem 3-En büyük asal bölen(PHP ve Perl)

Selamlar,
Bu yazıda Euler Problem 3’ten bahsedeceğim.Bu problem asal sayılar ile ilgili.Problemin orijinal hali aşağıdaki gibi.

Bu problem bize 13195 sayısını bölen asal sayıları 5,7,13 ve 29 olarak vermiş.Bizden 600851475143 sayısını bölen en büyük asal sayıyı istiyor. 

Öncelikle bir sayı asal mı değil mi nasıl buluruz ona bakalım. 

Elimizde bir sayı var örneğin 11 sayısını ele alalım.

• Öncelikle bu sayının karekökünü alıyoruz. Bulduğumuz sayı 3.3166247903554
• Daha sonra bu sayının tam kısmına 1 ekliyoruz. (3.3166247903554 sayısının tam kısmı 3) Sonuç olarak 4 sayısını buluyoruz.
• Son olarak 11 sayısının 4’e kadar olan sayılara tam bölünüp bölünmediğine bakıyoruz.Eğer hiç birine tam olarak bölünmüyor ise sayımız asal sayı oluyor. Bir tanesine bile tam bölünüyorsa sayımıza asal sayı demiyoruz.Bizim 11’imiz 1,2,3 ten hiç birine tam bölünmüyor. Bu yüzden 11 asal sayı oluyor.(Gerçi hiç bir sayıya bölünmediği için mi asal diyoruz yoksa asal olduğu için mi hiç bir sayıya bölünmüyor bunun cevabını bilmiyorum 😀 )

Tabi bu yöntem asal sayı bulmada tek yöntem değil. Daha fazla bilgi için buraya bakabilirsiniz.

Sayımızın asal olup olmadığını test ettikten sonra bizden istenen kısma geçebiliriz. Öyle bir sayı bulacağız ki 600851475143 sayısını tam bölecek ve aynı zamanda asal olacak.

Bunun için 1 den 600851475143 sayısına kadar ilerleyen bir döngü kullanıp döngünün her bir sayısının asal sayı ve 600851475143 sayısının böleni olup olmadığına bakmamız yeterli olacak.

Ben asal sayı mı değil mi sorusunun cevabı olarak asalTest diye bir fonksiyon oluşturdum ve sayının asal olup olmadığının kontrolünü bu fonksiyonla hesaplattım.Bu problemin çözümü için PHP ve Perl dillerinde yazdığım kodları vereceğim.

PHP Kodları:

<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<!--
Ümit ŞEN
izmir bornova evka-4
18 Haziran 2013 15:32

Problem:
Largest prime factor
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
-->
<h2>Euler Problem 3-Largest prime factor</h2>
<form action="" method="POST">
<input type="text" name="sayi">
<input type="submit" value="Hesapla" name="hesapla">
</form>

<?php

if (isset($_POST['hesapla']) && !empty($_POST['sayi']))
{
	$sayi=(int)$_POST['sayi'];
	echo "Girilen Sayı : <font color='red'>".$sayi."</font><br>";
	//-------------------------------------------------------------------------------------
	//girilen sayı asal mı değil mi test etme
	function asalTest($n)
	{
		$s=(int)$n;
		//kontrol 1
		if ($s < 2)
		{
			return FALSE;
		}
		// kontrol 2
		if ($s==2)
		{
			return TRUE;
		}
		//Asal hesabı
		$k=(int)($s^0.5+1);
		for ($i=3; $i < $k; $i+=2)
		{
			if ($s % $i==0)
			{
				return FALSE;
			}
		}
		return TRUE;
	}
	//---------------------------------------------------------------------------------------------
	$a=1;
	while ($a < $sayi)
	{
		if ($sayi % $a == 0 and asalTest($a))
		{
			echo $a."<br>";
		}
		$a++;
	}

}else{
	echo "Lütfen sayı giriniz...<br>";
}
?>

Perl Kodları : 

#!/usr/bin/perl
#Ümit ŞEN
#izmir bornova evka-4
#18 Haziran 2013 15:32

#Problem:
#Largest prime factor
#Problem 3
#The prime factors of 13195 are 5, 7, 13 and 29.
#What is the largest prime factor of the number 600851475143 ?

$sayi=600851475143;
$k=asalTest($sayi);

$say=2;
while ($say<$sayi)
{
	if ($sayi % $say == 0)
	{
		$son = asalTest($say);
		if ($son == 1)
		{
			print("$say\n");
		}
	}
	$say++;
}

sub asalTest
{
	$asal=1;
	$s=int($_[0]);
	#kontrol 1
	if ($s<2)
	{
		$asal=0;
	}
	#kontrol 2
	if ($s==2)
	{
		$asal=1;
	}
	#asallar
	$kok=int(($s**0.5)+1);
	for ($i=2; $i<$kok; $i+=1)
	{
		if ($s % $i == 0)
		{
			$asal=0;
		}
	}
	return $asal;
}

Problemin bizden istediği sonuç ise 6857.

Buradan da programın genel sayılar için çözümünü video olarak izleyebilirsiniz.(Perl dili)

İyi günler… 😉