欧拉计划

0号问题

题目

如果一个数是某个正整数的平方，那么这个数就是完全平方数，或者简称平方数。 例如： 25 是一个平方数，因为 \(5^2 = 25\) 它也是一个奇数平方数。

前五个平方数是：[1,4,9,16,25]奇数平方数之和为 1 + 9 + 25 = 35 。

在前172000 个平方数中，所有奇数平方数的总和是多少？

题解

实际上就是计算

\[ 1^2 + 3^2 + 5^2 + .. + 171999^2 \]

其实这是一个等幂求和的问题,曾经我们学过:

\[ 1^2 + 2^2 + .. + n^2 = \frac{n (n+1) (2n+1)} \]

我们可以观察一下偶数的

\[ 2^2 + 4^2 + 6^2 + .. + n^2 = 4 (1^2 + 2^2 + 3^2 + ... + (\frac{n}{2})^2) = \frac{4 n (n+1) (2n+1)}{6} \]

我们减一下得到

\[ 1^2 + 3^2 + .. + (n-1)^2 = \frac{n (n-1) (n+2)}{6} \]

1号问题

题目

斐波那契数列中每一项都是由前两项相加得到的。从 1 和 2 开始，前 10 项将是：1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …和第一个条款如下: 1,2,3,5,8,13

考虑斐波那契数列中值不超过四百万的项，求偶数项之和。

题解

这个题枚举即可 主要是需要快速计算斐波那契数列的算法: 要么用比内公式O(1) 要么用矩阵快速幂O(logn)

fn main() {
    let mut sum = 0;
    let mut n = 0;
    loop {
        let fib_num = fib(n);
        if fib_num > 4_000_000 {
            break;
        }
        if fib_num % 2 == 0 {
            sum += fib_num;
        }
        n += 1;
    }
    println!("{}", sum);
}

pub fn fib(n: i32) -> i32 {
    if n <= 1 { return n;}

    let mut base = [[1,1],[1,0]];
    let mut pow = n -1;
    let mut result =  [[1, 0], [0, 1]];
    while pow > 0 {
        if pow &1 == 1 {
            result = mul(&result,&base);
        }
        base = mul(&base,&base);
        pow >>= 1;
    }
    result[0][0]
}

fn mul(a: &[[i32; 2]; 2], b: &[[i32; 2]; 2]) -> [[i32; 2]; 2] {
    [
        [a[0][0] * b[0][0] + a[0][1] * b[1][0],
         a[0][0] * b[0][1] + a[0][1] * b[1][1]],
        [a[1][0] * b[0][0] + a[1][1] * b[1][0],
         a[1][0] * b[0][1] + a[1][1] * b[1][1]],
    ]
}

3号问题

The prime factors of 13195 are 5,7,13 and 29.

What is the largest prime factor of the number 600851475143 ?

题解

这本质上就是个质因数分解 用试除法或者Pollard Rho算法即可