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

B1tetheDust

1. import time
   
2. import math
   
3. 
   
4. 
   
5. # Method 1-------------------------------------------------------------------------------------------------------------#
   
6. def func1(num_range):
   
7.     divisors = [i for i in range(1, num_range + 1)]
   
8.     is_divisible = min_div_num = 0
   
9.     while not is_divisible:
   
10.         min_div_num += 30
    
11.         is_divisible = min((min_div_num % num == 0) for num in divisors)
    
12.     return min_div_num
    
13. 
    
14. 
    
15. # Method 2-------------------------------------------------------------------------------------------------------------#
    
16. def find_prime(a_num):
    
17.     is_prime = 1
    
18.     for i in range(2, int(math.sqrt(a_num) + 1)):
    
19.         if a_num % i == 0:
    
20.             is_prime = 0
    
21.     return is_prime
    
22. 
    
23. 
    
24. def func2(num_range):
    
25.     divisors = [i for i in range(1, num_range + 1)]
    
26.     primes = [j for j in divisors if find_prime(j)]
    
27.     mult = 1
    
28.     for k in primes:
    
29.         mult *= k
    
30.     min_div_num = is_divisible = 0
    
31.     while not is_divisible:
    
32.         min_div_num += mult
    
33.         is_divisible = min((min_div_num % num == 0) for num in divisors)
    
34.     return min_div_num
    
35. 
    
36. 
    
37. # Method 3-------------------------------------------------------------------------------------------------------------#
    
38. def gcd(num_a, num_b):
    
39.     if num_a == num_b:
    
40.         return num_a
    
41.     elif num_a < num_b:
    
42.         num_a, num_b = num_b, num_a
    
43.         return gcd(num_a, num_b)
    
44.     else:
    
45.         mod_a, mod_b = num_a & 1, num_b & 1
    
46.         if mod_a and mod_b:
    
47.             return gcd(num_b, num_a - num_b)
    
48.         elif not mod_a and mod_b:
    
49.             return gcd(num_a >> 1, num_b)
    
50.         elif mod_a and not mod_b:
    
51.             return gcd(num_a, num_b >> 1)
    
52.         else:
    
53.             return gcd(num_a >> 1, num_b >> 1) << 1
    
54. 
    
55. 
    
56. def lcm(num_a, num_b):
    
57.     gcdivisor = gcd(num_a, num_b)
    
58.     return (num_a * num_b) / gcdivisor
    
59. 
    
60. 
    
61. def func3(num_range):
    
62.     lcmultiple = 1
    
63.     for i in range(1, num_range + 1):
    
64.         lcmultiple = lcm(int(lcmultiple), int(i))
    
65.     return lcmultiple
    
66. 
    
67. 
    
68. # Method 4-------------------------------------------------------------------------------------------------------------#
    
69. def gcd1(num1, num2):
    
70.     if num1 < num2:
    
71.         num1, num2 = num2, num1
    
72.     while num2 != 0:
    
73.         num1, num2 = num2, num1 % num2
    
74.     return num1
    
75. 
    
76. 
    
77. def lcm1(num1, num2):
    
78.     gcdivisor = gcd1(num1, num2)
    
79.     a = num1 * num2 / gcdivisor
    
80.     return a
    
81. 
    
82. 
    
83. def func4(num_range):
    
84.     lcmultiple = 1
    
85.     for i in range(1, num_range + 1):
    
86.         lcmultiple = lcm1(int(lcmultiple), int(i))
    
87.     return lcmultiple
    
88. 
    
89. 
    
90. #----------------------------------------------------------------------------------------------------------------------#
    
91. test_num = 20
    
92. #----------------------------------------------------------------------------------------------------------------------#
    
93. start1 = time.perf_counter()
    
94. print('The smallest positive number is %d' % func1(test_num))
    
95. print('Method 1 takes %f s' % (time.perf_counter() - start1))
    
96. #----------------------------------------------------------------------------------------------------------------------#
    
97. start2 = time.perf_counter()
    
98. print('The smallest positive number is %d' % func2(test_num))
    
99. print('Method 2 takes %f s' % (time.perf_counter() - start2))
    
100. #----------------------------------------------------------------------------------------------------------------------#
     
101. start3 = time.perf_counter()
     
102. print('The smallest positive number is %d' % func3(test_num))
     
103. print('Method 3 takes %f s' % (time.perf_counter() - start3))
     
104. #----------------------------------------------------------------------------------------------------------------------#
     
105. start4 = time.perf_counter()
     
106. print('The smallest positive number is %d' % func4(test_num))
     
107. print('Method 4 takes %f s' % (time.perf_counter() - start4))

复制代码

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

Asss-whom

Rust + Rayon并行无脑暴算：

1. use rayon::prelude::*;
   
2. use std::time::Instant;
   
3. 
   
4. fn main() {
   
5.     let now = Instant::now();
   
6.     let mut start = 1;
   
7.     let mut i = None;
   
8.     while i == None {
   
9.         i = (start..start+1000)
   
10.         .into_par_iter()
    
11.         .filter(|x| check(*x))
    
12.         .min();
    
13.         start += 1000;
    
14.     }
    
15.    
    
16.     println!("最小数字是{:?}", i);
    
17.     println!("耗时{}毫秒。", now.elapsed().as_millis())
    
18. }
    
19. 
    
20. fn check(num: i32) -> bool {
    
21.     for i in 1..21 {
    
22.         if num % i != 0 {
    
23.             return false;
    
24.         }
    
25.     }
    
26.     true
    
27. }

复制代码

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

Eca

1. #include <stdio.h>
   
2. 
   
3. /*
   
4. 2520 是最小的能被 1-10 中每个数字整除的正整数。
   
5. 
   
6. 最小的能被 1-20 中每个数整除的正整数是多少？
   
7. */
   
8. 
   
9. int divisor(int num, int d) {
   
10.         return (num / d == (float)num / (float)d);
    
11. }
    
12. 
    
13. int count(int n, int x) {
    
14.         for (int i = 1; i <= x; i++)
    
15.                 if (!divisor(n, i))
    
16.                         return 0;
    
17. 
    
18.         return 1;
    
19. }
    
20. 
    
21. int main() {
    
22.         int i = 1;
    
23.         while (!count(i, 20))
    
24.                 i++;
    
25.         printf("%d", i);
    
26.         return 0;
    
27. }
    

复制代码

希望大神指出优化方法

Eca

1. #include <stdio.h>
   
2. 
   
3. /*
   
4. 2520 是最小的能被 1-10 中每个数字整除的正整数。
   
5. 
   
6. 最小的能被 1-20 中每个数整除的正整数是多少？
   
7. */
   
8. 
   
9. #define ll long long
   
10. 
    
11. int divisor(ll int num, ll int d) {
    
12.         return (num / d == (double)num / (double)d);//float好像放不下一些大的值
    
13. }
    
14. 
    
15. int count(int n, int x) {
    
16.         if (!n)
    
17.                 return 0;
    
18.         for (int i = 1; i <= x; i++)
    
19.                 if (!divisor(n, i))
    
20.                         return 0;
    
21.         return 1;
    
22. }
    
23. 
    
24. int main() {
    
25.         ll int i = 6, max = 10;
    
26.         ll int t = 0;
    
27.         for (int j = 2; j <= max; j++)
    
28.                 if (j % 2 != 0)
    
29.                         if (j % 3 != 0)
    
30.                                 i *= j;
    
31.         while (!count(t, max))
    
32.                 t += i;
    
33. 
    
34.         printf("%lld", t);
    
35. 
    
36.         return 0;
    
37. }
    

复制代码

Kazimierz

1ms

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long LL;
   
5. 
   
6. LL gcd(LL a,LL b)
   
7. {
   
8.     return b?gcd(b,a%b):a;
   
9. }
   
10. 
    
11. LL lcm(LL a,LL b)
    
12. {
    
13.     return a*b/gcd(a,b);
    
14. }
    
15. 
    
16. int main()
    
17. {
    
18.     LL ans = 1;
    
19.     for(int i=1;i<=20;i++) ans = lcm(ans,i);
    
20.     cout<<ans<<endl;
    
21.     return 0;
    
22. }

复制代码

叶落了

#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

1. for i in range(2520, 1000000000):
   
2.     for j in range(10, 21):
   
3.         if i % j == 0:
   
4.             if j == 20:
   
5.                 print(i)
   
6.                 break
   
7.         else:
   
8.             break

复制代码

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

Ian_Li

c++ 练习

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int multiple(int a, int b);
   
5. 
   
6. int main() {
   
7.     int a = 2;
   
8.     for (int i = 3; i <= 20; i++) {
   
9.         a = multiple(a, i);
   
10.     }
    
11.     cout << a << endl;
    
12.     return a;
    
13. }
    
14. 
    
15. int multiple(int a, int b) {
    
16.     if (a > b) {
    
17.         return multiple(b, a);
    
18.     }
    
19.     int m = b;
    
20.     while (m % a || m % b) {
    
21.         m = m + b;
    
22.     }
    
23.     return m;
    
24. }

复制代码