题目5：找出最小的能被1-20中每个数整除的数

Kazimierz

大概跑了3s 结果232792560

#include <stdio.h>

int main()
{
        int num=20,i=1;
        loop:
        {
                num+=1;
                for(i=1;i<=20;i++)
                {
                        if(num%i!=0)
                        {
                                goto loop;
                        }
                }
        }
        
        printf("%d",num);
        return 0;
}

jerryxjr1220

用“动态规划”的思想求解，其实很方便。
要求的数需要被1~20内所有的数整除，那么化繁为简，如果只要求这个数被1~2整除，那么这个数就是1和2的最小公倍数，1~3整除就是1~2的最小公倍数与3的最小公倍数，以此类推一直到20，所以题目就可以简化成求2个数的最小公倍数，然后循环20次就完了。
go代码：

package main

import (
        "fmt"
        "math"
        "time"
)

//题目5：
//
//2520 是最小的能被 1-10 中每个数字整除的正整数。
//
//最小的能被 1-20 中每个数整除的正整数是多少？
func max_elem(a, b int64) int64 {
        x := int64(math.Max(float64(a), float64(b)))
        y := int64(math.Min(float64(a), float64(b)))
        t := x % y
        for {
                if t != 0 {
                        x = y
                        y = t
                        t = x % y
                } else {
                        return y
                }
        }
}

func min_fact(a, b int64) int64 {
        return a * b / max_elem(a, b)
}

func main() {
        t := time.Now()
        var i, j int64 = 2, 1
        for i = 2; i < 21; i++ {
                j = min_fact(j, i)
        }
        fmt.Println(j)
        tt := time.Now()
        fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}

输出：

C:\Users\Anaconda\GolandProjects\EulerProject\output\go_build_Euler05_go.exe
232792560
耗时： 0 ms

进程 已完成，退出代码为 0

1毫秒都不用

B1tetheDust

import time
import math


# Method 1-------------------------------------------------------------------------------------------------------------#
def func1(num_range):
    divisors = [i for i in range(1, num_range + 1)]
    is_divisible = min_div_num = 0
    while not is_divisible:
        min_div_num += 30
        is_divisible = min((min_div_num % num == 0) for num in divisors)
    return min_div_num


# Method 2-------------------------------------------------------------------------------------------------------------#
def find_prime(a_num):
    is_prime = 1
    for i in range(2, int(math.sqrt(a_num) + 1)):
        if a_num % i == 0:
            is_prime = 0
    return is_prime


def func2(num_range):
    divisors = [i for i in range(1, num_range + 1)]
    primes = [j for j in divisors if find_prime(j)]
    mult = 1
    for k in primes:
        mult *= k
    min_div_num = is_divisible = 0
    while not is_divisible:
        min_div_num += mult
        is_divisible = min((min_div_num % num == 0) for num in divisors)
    return min_div_num


# Method 3-------------------------------------------------------------------------------------------------------------#
def gcd(num_a, num_b):
    if num_a == num_b:
        return num_a
    elif num_a < num_b:
        num_a, num_b = num_b, num_a
        return gcd(num_a, num_b)
    else:
        mod_a, mod_b = num_a & 1, num_b & 1
        if mod_a and mod_b:
            return gcd(num_b, num_a - num_b)
        elif not mod_a and mod_b:
            return gcd(num_a >> 1, num_b)
        elif mod_a and not mod_b:
            return gcd(num_a, num_b >> 1)
        else:
            return gcd(num_a >> 1, num_b >> 1) << 1


def lcm(num_a, num_b):
    gcdivisor = gcd(num_a, num_b)
    return (num_a * num_b) / gcdivisor


def func3(num_range):
    lcmultiple = 1
    for i in range(1, num_range + 1):
        lcmultiple = lcm(int(lcmultiple), int(i))
    return lcmultiple


# Method 4-------------------------------------------------------------------------------------------------------------#
def gcd1(num1, num2):
    if num1 < num2:
        num1, num2 = num2, num1
    while num2 != 0:
        num1, num2 = num2, num1 % num2
    return num1


def lcm1(num1, num2):
    gcdivisor = gcd1(num1, num2)
    a = num1 * num2 / gcdivisor
    return a


def func4(num_range):
    lcmultiple = 1
    for i in range(1, num_range + 1):
        lcmultiple = lcm1(int(lcmultiple), int(i))
    return lcmultiple


#----------------------------------------------------------------------------------------------------------------------#
test_num = 20
#----------------------------------------------------------------------------------------------------------------------#
start1 = time.perf_counter()
print('The smallest positive number is %d' % func1(test_num))
print('Method 1 takes %f s' % (time.perf_counter() - start1))
#----------------------------------------------------------------------------------------------------------------------#
start2 = time.perf_counter()
print('The smallest positive number is %d' % func2(test_num))
print('Method 2 takes %f s' % (time.perf_counter() - start2))
#----------------------------------------------------------------------------------------------------------------------#
start3 = time.perf_counter()
print('The smallest positive number is %d' % func3(test_num))
print('Method 3 takes %f s' % (time.perf_counter() - start3))
#----------------------------------------------------------------------------------------------------------------------#
start4 = time.perf_counter()
print('The smallest positive number is %d' % func4(test_num))
print('Method 4 takes %f s' % (time.perf_counter() - start4))

前两个是自己想的，后面两个都借鉴了别人的算法，最快的是Method 4，还是别人的方法快。Sigh.

Asss-whom

Rust + Rayon并行无脑暴算：

use rayon::prelude::*;
use std::time::Instant;

fn main() {
    let now = Instant::now();
    let mut start = 1;
    let mut i = None;
    while i == None {
        i = (start..start+1000)
        .into_par_iter()
        .filter(|x| check(*x))
        .min();
        start += 1000;
    }
    
    println!("最小数字是{:?}", i);
    println!("耗时{}毫秒。", now.elapsed().as_millis())
}

fn check(num: i32) -> bool {
    for i in 1..21 {
        if num % i != 0 {
            return false;
        }
    }
    true
}

---
最小数字是Some(232792560)
耗时3147毫秒。
能把Rust写的这么慢的只有我了

Eca

#include <stdio.h>

/*
2520 是最小的能被 1-10 中每个数字整除的正整数。

最小的能被 1-20 中每个数整除的正整数是多少？
*/

int divisor(int num, int d) {
        return (num / d == (float)num / (float)d);
}

int count(int n, int x) {
        for (int i = 1; i <= x; i++)
                if (!divisor(n, i))
                        return 0;

        return 1;
}

int main() {
        int i = 1;
        while (!count(i, 20))
                i++;
        printf("%d", i);
        return 0;
}

希望大神指出优化方法

Eca

#include <stdio.h>

/*
2520 是最小的能被 1-10 中每个数字整除的正整数。

最小的能被 1-20 中每个数整除的正整数是多少？
*/

#define ll long long

int divisor(ll int num, ll int d) {
        return (num / d == (double)num / (double)d);//float好像放不下一些大的值
}

int count(int n, int x) {
        if (!n)
                return 0;
        for (int i = 1; i <= x; i++)
                if (!divisor(n, i))
                        return 0;
        return 1;
}

int main() {
        ll int i = 6, max = 10;
        ll int t = 0;
        for (int j = 2; j <= max; j++)
                if (j % 2 != 0)
                        if (j % 3 != 0)
                                i *= j;
        while (!count(t, max)) 
                t += i;

        printf("%lld", t);

        return 0;
}

Kazimierz

1ms

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}

LL lcm(LL a,LL b)
{
    return a*b/gcd(a,b);
}

int main()
{
    LL ans = 1;
    for(int i=1;i<=20;i++) ans = lcm(ans,i);
    cout<<ans<<endl;
    return 0;
}

叶落了

#include<stdio.h>
#include<math.h>

int Determine(int i);
int Determine(int i)
{
        int n;
        if(i==1)
        {
                return 0;
        }
        if(i==2)
        {
                return i;
        }
        else if(i%2==0)
        {
                return 0;
        }
        else
        {
                for(n=2;n<=pow(i,0.5);n++)
                {
                        if(i%n==0)
                        {
                                return 0;
                        }
                }
                return i;
        }
}

int main(void)
{
        int i,k;
        unsigned long long int sum=1;
       
        for(i=1;i<=20;i++)
        {
                k=Determine(i);
                if(k)
                {
                        for(k;k*k<=20;k=k*k)
                        {
                                ;
                        }
                        printf("%d\n",k);
                        sum=sum*k;
                }
        }
        printf("最小的能被 1-20 中每个数整除的正整数是%lld\n",sum);
        return 0;
}

//思路
/*
2->2
3->3
2->4
5->5

7->7
2->8
3->9

11->11

13->13


2->16
17->17

19->19

利用一个定理，任何一个合数都可以拆成 质数积 形式，用集合(且可以多同一元素)取并集

还可以质数的次方判断
但必须引入一个纯合数的概念，质数积 形式=全部为同一个质数。
在它的前面，不可能有比它还需要（在数量上）这同一个质数的数了
*/

qingyunvi

for i in range(2520, 1000000000):
    for j in range(10, 21):
        if i % j == 0:
            if j == 20:
                print(i)
                break
        else:
            break

答案是232792560，算法耗时比较长

Ian_Li

c++ 练习

#include <iostream>
using namespace std;

int multiple(int a, int b);

int main() {
    int a = 2;
    for (int i = 3; i <= 20; i++) {
        a = multiple(a, i);
    }
    cout << a << endl;
    return a;
}

int multiple(int a, int b) {
    if (a > b) {
        return multiple(b, a);
    }
    int m = b;
    while (m % a || m % b) {
        m = m + b;
    }
    return m;
}