Проект Euler Puzzler (особенно на PHP)

Question

Есть еще один недавний вопрос Project Euler, но я думаю, что он немного более конкретен (меня действительно интересуют только решения на основе PHP), поэтому я все равно спрашиваю.

Вопрос № 5 задает вам вопрос: «Какое наименьшее число делится на все числа от 1 до 20?»

Теперь я решил это дважды. Когда-то очень неэффективно, а иногда гораздо эффективнее, но я все еще далек от особенно изощренного ответа (и я не особенно хорош в математике, поэтому мое решение грубой силы). Я вижу несколько областей, в которых я мог бы улучшить это, но мне интересно, сможет ли кто-нибудь из вас продемонстрировать более эффективное решение этой проблемы.

* спойлер: вот мое менее чем оптимальное (7 секунд для запуска), но все еще терпимое решение (не уверен, что делать с двойным $ ... просто притворись, что видишь только 1 ...

    function euler5(){
        $x = 20;

        for ($y = 1; $y < 20; $y++) {

            if (!($x%$y)) {

            } else {  
                $x+=20;
                $y = 1;  
            }   

        }echo $x;
     };

Answer 1

Соберите простые множители для всех чисел от 1 до 20. Подсчитав максимальные показатели каждого простого множителя, мы получим 16 = 2**4, 9 = 3**2, а также 5, 7, 11, 13, 17, 19 (каждый появляется только однажды). Умножьте лот, и вы получите ответ.

Answer 2

в php это будет выглядеть так:

<?php
function gcd($a,$b) {
    while($a>0 && $b>0) {
        if($a>$b) $a=$a-$b; else $b=$b-$a;        
    }
    if($a==0) return $b;
    return $a;
}
function euler5($i=20) {
    $euler=$x=1;
    while($x++<$i) {
        $euler*=$x/gcd($euler,$x);
    }
    return $euler;
}

?>

Это как минимум вдвое быстрее, чем вы опубликовали.

Answer 3

Вы можете удалить некоторые числа, которые делятся на, например, 1 не нужен, все натуральные числа делятся на 1. Вам тоже не нужно 2, и, следовательно, все числа делятся на кратные 2 (4, 8 , 16 и т. Д.) Также делятся на 2. Таким образом, соответствующие цифры будут 11, 12, 13, 14, 15, 16, 17, 18 и 19.

Итак:

<?
function eulerPuzzle()
{
  $integers = array( 11,12,13,14,15,16,17,18,19 );

  for ($n = 20; 1; $n += 20 ) {
    foreach ($integers as $int) { 
      if ( $n % $int ) { 
    break; 
      }
      if ( $int == 19 ) { 
    die ("Result:" . $n); 
      }
    }
  }
}

eulerPuzzle();
?>

Answer 4

Крис Шут-Янг прав.

В общем, если вам нужно наименьшее число, которое делится равномерно на все числа от 1 до N, вам нужно найти все простые числа от 2 до N, и для каждого найти наибольшее число раз он делит любое число в диапазоне. Это можно рассчитать, найдя наибольшую мощность простого числа, не превышающую N.

В случае 20, как указал Крис, 2 ^ 4 - это наибольшая сила 2, не превышающая 20, а 3 ^ 2 - наибольшая сила 3, не превышающая 20, и только для всех других простых первая сила не больше 20.

Answer 5

<?php
$i=20;
while ($i+=20) {
    for ($j=19;$j!==10;--$j){
        if ($i%$j) continue 2;
    }
    die ("result: $i\n");
}

На сегодняшний день это самое быстрое и короткое решение для php. Примерно в 1,4 раза быстрее, чем Czimi на моем компе. Но посмотрите на решение Python, это хороший алгоритм.

Answer 6

@ Люди занимаются простой математикой; Я не уверен, является ли это целью упражнения. Вы должны изучать новые языки и новые способы выполнять вещи. Просто делать это с помощью калькулятора - это неправильный путь.

И я знаю, что это сообщение в старой ветке, но оно все равно появляется в результатах Google:)

Делая это в коде (то есть PHP), я нашел, что это самое быстрое решение:

function eulerPuzzle() {
    $integers = array (11, 12, 13, 14, 15, 16, 17, 18, 19 );

    for($n = 2520; 1; $n += 2520) {
        foreach ( $integers as $int ) {
            if ($n % $int) {
                break;
            }
            if ($int == 19) {
                die ( "Result:" . $n );
            }
        }
    }
}

eulerPuzzle ();

Да, это модифицированная часть от CMS. Основная причина того, что он быстрее, заключается в том, что когда вы читаете вопрос, они уже заявляют, что наименьшее возможное число для первых 10 целых чисел равно 2520. Поэтому вы можете просто увеличить его на 2520 вместо 20. В результате число циклов в 126 раз меньше *

Answer 7

Некоторые люди действительно обдумывают это ...

в рубине:

puts 5*7*9*11*13*16*17*19

Answer 8

Я знаю, что вы сказали PHP, но вот мой набросок на Python.

#!/usr/bin/env python

from operator import mul

def factor(n):
    factors = {}
    i = 2
    while i < n and n != 1:
        while n % i == 0:
            try:
                factors[i] += 1
            except KeyError:
                factors[i] = 1
            n = n / i
        i += 1
    if n != 1:
        factors[n] = 1
    return factors

base = {}
for i in range(2, 2000):
    for f, n in factor(i).items():
        try:
            base[f] = max(base[f], n)
        except KeyError:
            base[f] = n

print reduce(mul, [f**n for f, n in base.items()], 1)

Это не так элегантно, как я мог бы это сделать, но он вычисляет наименьшее общее число от 2 до 2000 в .15 с. Если ваше итеративное решение может обрабатывать миллиард кандидатов в секунду, для его завершения потребуется 10 ^ 849 лет.

Другими словами, не пытайтесь оптимизировать неправильный алгоритм.