Решение (ответы) задач Эйлера (Euler) на PHP (задачи 1 — 10)

Для тренировки решения алгоритмов, а это база любого программиста, есть отличный ресурс: проект Эйлера, с задачами, уровень сложности которых усложняется по мере их возрастания. Всего задач в проекте более 700-та, напротив каждой показано количество пользователей ее решивших.

Если решить самостоятельно 50 первых задач или хотя бы проанализировать и понять как они выполняются, можно сказать, что вы достигли хорошего уровня в программировании алгоритмов.

В данной статье будут решены и проанализированы первые 10-ть задач.

1. Числа, кратные 3 или 5

Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел равна 23.

Найдите сумму всех чисел меньше 1000, кратных 3 или 5.

Решение:

function task1($num) {
    $sum = 0;
    for ($i = 0; $i < $num; $i++){
		if ($i % 3 == 0 || $i % 5 == 0) {
			$sum = $sum + $i;
		}
	}
return $sum;	
}
$res1 = task1(1000);
echo $res1; // 233168

2. Четные числа Фибоначчи

Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих. Начиная с 1 и 2, первые 10 элементов будут: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Найдите сумму всех четных элементов ряда Фибоначчи, которые не превышают четыре миллиона.

Решение:

function task2($limit){
    $sum = 0;
    $a = 0;
    $b = 1;

    while ($b < $limit){
        if ($b % 2 == 0) {
            $sum = $sum + $b;
        }
        $h = $a + $b;
        $a = $b;
        $b = $h;
    }
    return $sum;
}

$res2 = task2(4000000);
echo $res2; // 4613732

3. Наибольший простой делитель

Простые делители числа 13195 — это 5, 7, 13 и 29.

Каков самый большой делитель числа 600851475143, являющийся простым числом?

Решение:

set_time_limit(300);
function isPrime($n) {
    for($i = 2; $i <= sqrt($n); $i++) {
        if($n % $i == 0) {
            return false;
        }
    }
    return true;
}

function task3($limit) {
	$max = 0;
    for ($i = 1; $i < $limit; $i++) {
        if (isPrime($i) && $limit % $i == 0) {
            $max = $i;
        }
    }
    return $max;
}
$res3 = task3(600851475143);
echo $res3; // 6857

Вышеуказанное решение правильное, но с большими числами оно не будет работать. Для этого есть решение №2:

function task3($n)
{
    $i = 2;

    while ($i * $i < $n) {
        while ($n % $i == 0) {
            $n = $n / $i;
        }
        $i = $i + 1;
    }
    return $n;
}
$res3 = task3(600851475143);
echo $res3; // 6857

4. Наибольшее произведение-палиндром

Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел – 9009 = 91 × 99.

Найдите самый большой палиндром, полученный умножением двух трехзначных чисел.

Решение:

function isPalindrome($palindrom) {
    $palindrom = strval($palindrom);
    $pal = strlen($palindrom) - 1;
    for ($i = 0; $i < $pal; $i++) {
        if ($palindrom[$i] !== $palindrom[$pal - $i]) {
            return false;
        }
    }
    return true;
}
function largestPalindrome(){
    $largestPalindrome = 0;
    for ($a = 100; $a <= 999; $a++) {
        for ($b = 100; $b <= 999; $b++) {
            if (isPalindrome($a * $b) and $a * $b > $largestPalindrome) {
                $largestPalindrome = $a * $b;
            }
        }
    }
    return $largestPalindrome;
}
$res4 = largestPalindrome();
echo $res4; // 906609

5. Наименьшее кратное

2520 — самое маленькое число, которое делится без остатка на все числа от 1 до 10.

Какое самое маленькое число делится нацело на все числа от 1 до 20?

Решение:

function isDevisible($number) {
    for ($i = 2; $i < 21; $i++) {
        if ($number % $i != 0) {
            return 'false';
        }
    }
    return 'true';
}

$number = 20;
while (true) {
    if (isDevisible($number)) {
        break;
    } else {
        $number = $number + 20;
    }
}
echo $number; // 232792560

6. Разность между суммой квадратов и квадратом суммы

Сумма квадратов первых десяти натуральных чисел равна 12 + 22 + … + 102 = 385

Квадрат суммы первых десяти натуральных чисел равен(1 + 2 + … + 10)2 = 552 = 3025

Следовательно, разность между суммой квадратов и квадратом суммы первых десяти натуральных чисел составляет 3025 − 385 = 2640.

Найдите разность между суммой квадратов и квадратом суммы первых ста натуральных чисел.

Решение:

function difNatural(){
    $sum_kv = 0;
    for ($i = 1; $i < 101; $i++) {
        $sum = $i * $i;
        $sum_kv = $sum_kv + $sum;
    }
    $sum1 = 0;
    for ($j = 1; $j < 101; $j++) {
        $sum1 = $sum1 + $j;
    }
    $sum_kv1 = pow($sum1, 2);
    return ($sum_kv1 - $sum_kv);
}

$res6 = difNatural();
echo $res6;//25164150

7. 10001-ое простое число

Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-ое простое число — 13.

Какое число является 10001-ым простым числом?

Решение:

function isPrime($n) {
    for($i = 2; $i <= sqrt($n); $i++) {
        if($n % $i == 0) {
            return false;
            break;
        }
    }
    return true;
}

function nthPrime($n){
    $count = 0;
    $inc = 2;
    while ($count < $n) {
        if (isPrime($inc)) {
            $count++;
            echo "</br>";
        }
        $inc++;
    }
    return $inc - 1;
}

$res7 = nthPrime(10);
echo $res7; // 104743

8. Наибольшее произведение в последовательности

Наибольшее произведение четырех последовательных цифр в нижеприведенном 1000-значном числе равно 9 × 9 × 8 × 9 = 5832.

731671765313 … 2963450

Найдите наибольшее произведение тринадцати последовательных цифр в данном числе.

Решение:

$num = '731671765313306249192 .... 2963450';
function max_mul($num){
    $p = strval($num);
    $pa = strlen($num) - 12;
    $st = 0;
    $n = 13;
    for ($i = 0; $i < $pa; $i++){
        $sum = 1;
        for ($j = 0; $j < $n; $j++) {
            $sum = $sum * $p[$i + $j];
        }
        if ($sum > $st) {
            $st = $sum;
        }
    }
    return $st;
}

$res8 = max_mul($num);
echo $res8;// 23514624000

9. Особая тройка Пифагора

Тройка Пифагора — три натуральных числа a < b < c, для которых выполняется равенствоa2 + b2 = c2

Например, 32 + 42 = 9 + 16 = 25 = 52.

Существует только одна тройка Пифагора, для которой a + b + c = 1000.
Найдите произведение abc.

Решение:

function numPifagor()
{
    for ($a = 1; $a < 1000; $a++) {
        for ($b = 1; $b < $a; $b++) {
            $c = 1000 - $a - $b;
            if (((pow($a, 2)) + (pow($b, 2)) === (pow($c, 2))) &&
                ($a + $b + $c === 1000)) {
                return $a * $b * $c;
            }
        }
    }
}

$res9 = numPifagor();
echo $res9 ; //31875000

10. Сложение простых чисел

Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17.

Найдите сумму всех простых чисел меньше двух миллионов.

Решение:

set_time_limit(300);
function isPrime($n) {
    for($i = 2; $i <= sqrt($n); $i++) {
        if($n % $i == 0) {
            return false;
            break;
        }
    }
    return true;
}

function nthPrime($n){
        $inc = 2;
        $sum = 0;
        while ($inc < $n) {
            if (isPrime($inc)) {
                $sum = $inc + $sum;
            }
            $inc++;
        }
    return $sum;
}

$res7 = nthPrime(2000000);
echo $res7; //142913828922

Добавить комментарий