Some Exercises

IamZS 112 0

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

function multipleSum(num) {
    var i = 0,
        s = 0;
    while (i < num) {
        if (i % 3 === 0 || i % 5 === 0) {
            s += i;
        }
        i ++;
    }
    return s
}

console.log(multipleSum(1000))
def multipleSum(num):
    i, s = 0, 0
    while i < num:
        if i % 3 == 0 or i % 5 == 0:
            s += i
        i += 1
    return s

print(multipleSum(1000))

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

// 蠢办法
function fib(end) {
    var num1 = 0, num2 = 1, num3;
    var arr = [];
    for (var i=3; i<=end; i++) {
        num3 = num1 + num2;
        num1 = num2;
        num2 = num3;
        if (num3 > end) {
            break;
        }
        arr.push(num3);
    }
    return arr;
}
function sumEvenValue(n) {
    var s = 0;
    for (x of fib(n)) {
        if (x % 2 === 0) {
            s += x;
        }
    }
    console.log(s);
}
sumEvenValue(4000000);
// 直接找斐波那契数列中的偶数
function sumEvenFib(n) {
    var f1 = 1,
        f2 = 1,
        f3 = 2,
        sum = 0;
    while (f3 < n) {
        if (f3 % 2 === 0) {
            sum += f3;
        }
        f1 = f2;
        f2 = f3;
        f3 = f1 + f2;
    }
    return sum;
}
console.log(sumEvenFib(4000000));
def fib(end):
    num1, num2 = 1, 1
    arr = []
    while num2 <= end:
        arr.append(num2)
        num1, num2 = num2, num1+num2
    return arr
print(fib(150))

def sumEvenValue(n):
    s = 0
    for x in fib(n):
        if x % 2 == 0:
            s += x
    print(s)

sumEvenValue(4000000)

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

What is the largest prime factor of the number 600851475143 ?

分解质因数 -- Prime Factorization

比如要分解 45,其分解后为 3 * 3 * 5,质因数为 3, 3 和 5。要找到这些质因数,最简单的方法就是遍历 2, 3, 4, 5, 6, ..., k。

如果数 n 能被 k 整除,那么就重复整除它,直到不能除尽为止,然后再用 k+1 重复上述操作。

比如 45 / 2 不能除尽,那么前进到 3,45 / 3 = 15 能除尽,则 3 是其质因数;

然后继续用 3 去除,15 / 3 = 5,到 5 / 3 时不能除尽,则前进到下一个数 4。不行,再前进到 5,5 / 5 = 1,查找结束。

// 我的傻逼写法(一)
function positiveNum(n) {
    var x, arr = [];
    for (x=1; x<=n; x++) {
        arr.push(x);
    }
    return arr;
}

function get_primes(n) {
    arr = positiveNum(n);
    return arr.filter(function(y) {
        if (y === 1) {
            return false;
        }
        for (var i=2; i<=Math.sqrt(y); i++) {
            if (y % i === 0) {
                return false;
            }
        }
        return true;
    });
}

function divByPrime(num) {
    var L = [];
    arr = get_primes(num);
    for (x of arr) {
        if (num % x === 0) {
            L.push(x);
        }
    }
    return L;
}

// 遍历次数过多,太复杂,浏览器 console 崩溃
console.log(get_primes(600851475143));
console.log(divByPrime(600851475143));
// 正常写法
function divByPrime(num) {
    var arr = [], factor = 2;
    while (num > 1) {
        if (num % factor === 0) {
            while (num % factor === 0) {
                num /= factor;
                arr.push(factor);
            }
        }
        factor += (factor === 2 ? 1 : 2);
    }
    return arr;
}

console.log(divByPrime(13195));
console.log(divByPrime(600851475143));

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

// 最初版本,复杂
function maxPalindromeNum(len) {
    var start = Math.pow(10, len-1),
        end = Math.pow(10, len) - 1,
        arr = [],
        product;
    for (var i=start; i<=end; i++) {
        for (var j=start; j<=end; j++) {
            product = (i * j).toString();
            var reverseProduct = product.split('').reverse().join('');
            if (product === reverseProduct) {
                arr.push(product);
                // console.log(arr);
            }
        }
    }
    return arr.map(function(x) { return x * 1; }).sort(function(x, y) {
        if (x > y) { return -1; }
        if (x < y) { return 1; }
        else { return 0; }
    })[0];
}
console.log(maxPalindromeNum(2));
console.log(maxPalindromeNum(3));
// 第二版本
function maxPalindromeNum(len) {
    var start = Math.pow(10, len-1),
        end = Math.pow(10, len) - 1,
        arr = [],
        largest = 0,
        product;
    for (var i=start; i<=end; i++) {
        for (var j=start; j<=end; j++) {
            product = (i * j).toString();
            var reverseProduct = product.split('').reverse().join('');
            if (product === reverseProduct && (product * 1) > largest) {
                arr.push(product);
                largest = product * 1;
            }
        }
    }
    return largest;
}
console.log(maxPalindromeNum(2));
console.log(maxPalindromeNum(3));

另一种思路:

因为两个 n 位数的乘积一定小于 (Math.pow(10, len) - 1) * (Math.pow(10, len) - 1),既然要找满足条件的最大的回文数,所以可以从大往小找;

找到以后验证是否是两个 n 位数的乘积,这里也由大到小进行。首先看看能不能被 (Math.pow(10, len) - 1) 整除,如果能,检查商是不是 n 位数。否则,再减一进行查找。

温馨提示

算了,不再在博客上更新『欧拉计划』了,因为回过头去看会觉得代码真·写得跟屎一样(Coding Shit Code),一次次迭代,编辑起来太蛋疼,浪费时间。

发表评论
表情 图片 链接 代码