문제 1: 1000보다 작은 자연수 중에서 3과 5의 배수의 합을 구하세요.

<?php
/**
 * 找出1000以下自然数中3和5的倍数之和。
 *
 * @author 花生米
 * @date 2015-09-06
 * @desc php version 5.4.33
 */


$max = 1000;
$sum = 0;

/**
 * 方法1
 * 时间复杂度：O(n)
 */
if (0) {
    for ($i = 1; $i < $max; $i++) {
        if ($i % 3 == 0 || $i % 5 == 0) {
            $sum += $i;
        }
    }
}

/**
 * 方法2
 * 时间复杂度：O(n)
 * 循环次数较方法1少
 */
if (0) {
    for ($i = 3; $i < $max; $i += 3) {
        $sum += $i;
    }
    for ($i = 5; $i < $max; $i += 5) {
        //排除被3和5同时整除的数
        if ($i % 3) {
            $sum += $i;
        }
    }
}
/**
 * 方法3(最优)
 * 时间复杂度：O(1)
 * 运用等差数列求和公式
 */
if (0) {
    $multiple3  = intval($max / 3);
    $multiple5  = intval($max / 5);
    $multiple15 = intval($max / 15);
    //$value：值 $multiple：倍数
    $total = function ($value, $multiple) {
        return $value * (1 + $multiple) * $multiple / 2;
    };

    $sum = $total(3, $multiple3) + $total(5, $multiple5) - $total(15, $multiple15);//减公倍数
}