第47题-不同的素因子数

本文包含欧拉项目第47题解

问题描述

第47题图

翻译为中文就是

14和15是2个连续的正整数，它们都有2个不一样的素因数，644，646，646是3个连续的正整数，它们各有3个不一样的素因数

求解，找到一组连续的4个正整数，使得每个数都有4个不同的素因数

解题思路

没别的思路，就是暴力破解，找到每个数字的素因数，然后判断条件。核心功能是素因数分解算法

rust语言实现

p47.rs

use algorithms::math::prime::get_uniq_prime_factors;

pub fn solution_of_p47() -> usize {
    let mut i = 2;
    loop {
        i += 1;
        let factors1 = get_uniq_prime_factors(i);
        let factors2 = get_uniq_prime_factors(i + 1);
        let factors3 = get_uniq_prime_factors(i + 2);
        let factors4 = get_uniq_prime_factors(i + 3);

        if factors1.len() == 4 && factors2.len() == 4 && factors3.len() == 4 && factors4.len() == 4
        {
            return i;
        }
    }
}

/// 以下2个方法都应该放在 prime 模块中
/// 素数分解算法
pub fn get_prime_factors(num: usize) -> Vec<usize> {
    let mut n = num;
    let mut result = vec![];
    while n % 2 == 0 {
        result.push(2);
        n /= 2;
    }
    for i in (3..=((n as f64).sqrt() as usize)).step_by(2) {
        while n % i == 0 {
            result.push(i);
            n /= i;
        }
    }
    if n > 2 {
        result.push(n);
    }
    return result;
}

/// 去重的素数分解算法
pub fn get_uniq_prime_factors(num: usize) -> Vec<usize> {
    let mut factors = get_prime_factors(num);
    factors.sort();
    factors.dedup();
    return factors;
}

代码很简单，但是我把素数分解相关算法放到 algorithms::math::prime 模块下了，把公共代码提取出来，构造自己的工具方法， 以后遇到类似的题目就不用重复发明轮子了。目前在这个素数模块下我放了 is_prime,get_prime_table,get_prime_factors, get_uniq_prime_factors 这4个适用方法，每个都经过了充分测试保证正确性，这种复用方式是不是很棒

在素因数分解算法中，先是把反复除2，经过这轮变换后，n一定是奇数，第二步用3、5、7...等一系列奇数去除n，因为素数肯定是奇数，所以经过这轮变换后，n不能被非自身的奇数除，第三步如果n大于2那么n肯定是素数，这个素数分解的算法也是挺巧妙的

核心算法搞定后，解法就一目了然了，就是简单的暴力破解，聪明的你有更优化的解法吗