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

python6

夜魔时生 发表于 2017-3-6 14:19

这个FOR 要运行很久。

何小胖胖

对于这个题，感觉可以由几种方面来减少运行时间，
第一就是要判断的数的选择，一个个往上加和一次加20，再对比求最大公约数求值最后时间会有很大不同
第二，优先用后面的去判断，能被20整除的一定能被2，4，5，10都整除，如果后面大的都不对，及早break，减少判断次数
第三，虽然我的代码不长，但是其中还有极大修改余地，尤其是数的选择，还能改进
#include<iostream>
using namespace std;
int main(){
        int num,temp=1;
        int i=20,j;
        while(i+=20){
                j=20;
                temp=1;
                for(j;j>2;j--){
                        if(i%j!=0){
                                temp=0;
                                break;
                        }
                }
                if(temp){
                        cout<<i;
                        break;
                }
        }
        return 0;
}

王小召

质子列表：[2, 2, 5, 19, 3, 3, 17, 2, 2, 7, 13, 11]
返回结果：232792560
用时：0.1092007s （实测:1000内基本时间不变，10000大概3.9s）



import time

#  获取num的质子列表
def get_primelist(num):
    num_list = []
    for i in range(2, num+1):
        while num % i == 0:
            num_list.append(i)
            num = num//i
    return num_list


# 判断范围内每个质子列表的值是不是已经存在，并且对数量进行比对，多则忽略少则补齐
def get_max(MAX_NUM):
    final_list = []
    result = 1
    for i in range(MAX_NUM):
        cur_num = get_primelist(MAX_NUM - i)
        for each in cur_num:
            x = final_list.count(each)
            y = cur_num.count(each)
            if x > y:
                pass
            else:
                for z in range(y - x):
                    final_list.append(each)
                cur_num.remove(each)
    print(final_list)
    for each in final_list:
        result *= each
    return result

print(get_max(100))
print(time.process_time())

成为极客

1. import time as t
   
2. start = t.perf_counter()
   
3. i = j = 11*13*17*19
   
4. list1 = [12,14,15,16,18,20]
   
5. s = 1
   
6. while s:
   
7.     for each in list1:
   
8.         if i % each != 0:
   
9.             i += j
   
10.             s = 1
    
11.             break
    
12.         else:
    
13.             s = 0
    
14. end = t.perf_counter()
    
15. print(i)
    
16. print(end - start)

复制代码

232792560
0.0015221600000000016

永恒的蓝色梦想

Python

1. from math import gcd
   
2. res = i = 1
   
3. 
   
4. while i <= 20:
   
5.     res *= i // gcd(res, i)
   
6.     i += 1
   
7. 
   
8. print(res)

复制代码

怀心抱素

1. # 两个数的最大公约数
   
2. def func(a, b):
   
3.     if a == 0:
   
4.         return b
   
5.     else:
   
6.         if b > a:
   
7.             a, b = b, a
   
8.         a = a % b
   
9.         return func(a, b)
   
10. 
    
11. # 两个数的最小公倍数
    
12. def func1(a, b):
    
13.     return a * b / func(a, b)
    
14. 
    
15. # 一个区间的最小公倍数
    
16. def func2(a=1, b=20):
    
17.     c = 1
    
18.     for a in range(a, b+1):
    
19.         c = func1(a, c)
    
20.     return c
    
21. 
    
22. print(func2(1,20))

复制代码

1666194196

#include <stdio.h>

void main(){
        //2520是最小的能够被1到10整除的数。
        //最小的能够被1到20整除的正数是多少？
        int i=1;
        while(1){//1到正无穷的循环，用来找出结果
                int j,flag=1;
                for(j=1;j<=10;j++){//1到10
                        if(i%j!=0){//这个数不能整除1到10跳出for循环,令标志为假。下面不输出i，也不跳出while循环
                                flag=0;
                                break;
                        }       
                }
                if(flag){
                        printf("%d",i);
                        break;
                }
                i++;
        }
       
}

就是要努力呀

//!!!求能被1-20整除的最小正整数就是求1-20内所有数的最小公倍数!!!
//最小公倍数 = 所有数公有的质因数的最大次方 * 每个数独有的质因数的最大次方
//2520 = 2 ^ 3 * 3 ^ 2 * 5 * 7

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

#define MAX 20  //修改MAX的值可以求任意1-MAX中的最小公倍数

void prime_factor(int i, int (*pfactor)[2]);//求1-20内每一个数的质因数

void prime_factor(int i, int (*pfactor)[2])
{
        int j = 2, k = 0;
        int count = 0;

        do
        {
                if(i % j == 0)//如果i % j == 0 说明j是i的质因数中的一个
                {
                        i /= j;
                        count++;//记录质因数j出现的次数

                        pfactor[k][0] = j;//存放i的质因数j
                        pfactor[k][1] = count > pfactor[k][1] ? count: pfactor[k][1];//存放质因数j的最大次方
                }
                else
                {
                        j++;
                        k++;
                        count = 0;
                }
        }
        while(i != 1);
}

int main(void)
{
        int i;
        unsigned int result = 1;
        int pfactor[MAX][2] = {0};//pfactor[][0] 存放质因数     pfactor[][1] 存放这个质因数出现的最大次方

        for(int i = 0; i < MAX; i++)//将pfactor每一项初始化为1
        {
                pfactor[i][0] = 1;
                pfactor[i][1] = 1;
        }

        for(i = 2; i <= MAX; i++)
        {
                prime_factor(i, pfactor);
        }

        for(int i = 0; i < MAX; i++)
        {
                result *= pow(pfactor[i][0], pfactor[i][1]);//result = 所有质因数的最大次方之积
        }

        printf("result = %u\n", result);

        return 0;
}

长大1/2

#include <stdio.h>
#define NUM 20

int main(){
        int num = NUM;
        int i;
        int array1[num];
        int array2[num];
        //初始化数组       
        for (i = 0;i<num;i++){
                if (i == 0){
                        array1[i]=1;
                }else{
                        array1[i] = array1[i-1] + 1;
                }
        }
        //找NUM以内的素数
        int k = 0;
        int j;
        for (j = num;j>=2;j--){
                int flag = 1;
                for(i=2;i<j;i++){
                        if (j % i == 0){
                                flag = 0;
                                break;
                        }
                }
                if (flag){
                        array2[k++] = j;
                }
       
        }
        //用短除法的方式求最小公倍数
        long long result = 1;

        while(1){
                for(j=0;j<k;j++){
                        int flag = 0;
                        for (i = 0;i < num;i++){
                                if(array1[i] % array2[j] == 0){
                                        array1[i] /= array2[j];
                                        flag = 1;
                                }
                        }
                        if (flag){
                                result = result * array2[j];
                        }

                }
                int count = 0;
                for(i=0;i<num;i++){
                        if (array1[i]==1){
                                count++;
                        }
                }
                if (count == num){
                        break;               
                }

        }
        printf("%ld\n",result);

        return 0;
}

长大1/2

#include <stdio.h>
#define NUM 20


long gcd(long long,long long );

int main(){
        long long result = 1;
        long i = 2;
        while(i<=NUM){
                result = result * i / gcd(result,i);
                printf("i = %ld\n",i);
                i++;
        }
        printf("result = %ld\n",result);

        return 0;
}
long gcd(long long a,long long b){
        long temp;
        while(b != 0){
                temp = a;
                a = b;
                b = temp % b;
        }
               
        return a;

}

代号-K

很多欧拉计划中解题方法都可以用质数来求解
感觉最简单的算法，速度应该是最快的
10: 2520
20:answer:232792560
30:answer:2329089562800
40:answer:5342931457063200

1. typedef long long ElementType;
   
2. void getMinNumberOfFlag( ElementType *answer, int flag)
   
3. {
   
4.     int array[flag] = {0};
   
5.     int temp[flag] = {0};
   
6.     int prime[flag] = {0};
   
7. 
   
8.     prime[0] = 2;
   
9.     int i = 1;
   
10.     int j = 2;
    
11.     int k = 0;
    
12.     bool yes = true;
    
13.     int value = j;
    
14. 
    
15.     while(true)
    
16.     {
    
17.         if(value > flag)
    
18.         {
    
19.             break;
    
20.         }
    
21.         k = 0;
    
22.         while( k < i)
    
23.         {
    
24.             while(value % prime[k] == 0)
    
25.             {
    
26.                 temp[prime[k]-1] += 1;
    
27.                 value /= prime[k];
    
28.                 yes = false;
    
29.             }
    
30.             if(value > prime[k])
    
31.             {
    
32.                 k++;
    
33.             }else
    
34.             {
    
35.                 break;
    
36.             }
    
37.         }
    
38.         if(yes)
    
39.         {
    
40.             prime[i++] = value;
    
41.             temp[value-1] = 1;
    
42.         }
    
43. 
    
44.         for(int my = 0; my < flag; my++)
    
45.         {
    
46.             if(array[my] < temp[my])
    
47.             {
    
48.                 array[my] = temp[my];
    
49.             }
    
50.             temp[my] = 0;
    
51.         }
    
52. 
    
53.         j += 1;
    
54.         value = j;
    
55.         yes = true;
    
56.     }
    
57. 
    
58.     for(j = 0; j < i; j++)
    
59.     {
    
60.         printf("%d\n",prime[j]);
    
61.     }
    
62. 
    
63.     printf("\n");
    
64.     *answer = 1;
    
65.     for(j = 0; j < flag; j++)
    
66.     {
    
67.         printf("%d\n", array[j]);
    
68.         *answer *= (int) pow(j+1, array[j]);
    
69.     }
    
70. }
    
71. 
    
72. int main(int argc, char *argv[])
    
73. {
    
74.     ElementType  ret;
    
75.     getMinNumberOfFlag(&ret, 30);
    
76.     printf("answer:%d\n",ret);
    
77.     return 0;
    
78. }

复制代码

永恒的蓝色梦想

C++ 0ms

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. 
   
5. 
   
6. int main() {
   
7.     ios::sync_with_stdio(false);
   
8. 
   
9.     unsigned x, y, temp, i, result = 1;
   
10. 
    
11. 
    
12.     for (i = 1; i <= 20; ++i) {
    
13.         x = result;
    
14.         y = i;
    
15. 
    
16.         while (y) {
    
17.             temp = x % y;
    
18.             x = y;
    
19.             y = temp;
    
20.         }
    
21. 
    
22.         result *= i / x;
    
23.     }
    
24. 
    
25. 
    
26.     cout << result << endl;
    
27.     return 0;
    
28. }

复制代码

永恒的蓝色梦想

代号-K 发表于 2020-3-12 18:28
很多欧拉计划中解题方法都可以用质数来求解
感觉最简单的算法，速度应该是最快的
10: 2520

其实只要求1-20的最小公倍数就可以了……

leon0149

1. def isOK(x):
   
2.     for i in range(1, 21):
   
3.         if x % i:
   
4.             return False
   
5.     else:
   
6.         return True
   
7. 
   
8. 
   
9. num = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19
   
10. i = num
    
11. while True:
    
12.     if isOK(i):
    
13.         break
    
14.     i += num
    
15. 
    
16. print(i)
    

复制代码

xuan1788

牡丹花下死做鬼 发表于 2015-7-19 21:57
不习惯用python 还是C写的没怎么优化 大概一秒不到点出的答案 232792560

感觉经典的最小公倍数辗除法和质数累加的原理由异曲同工之妙呀

辗除法：

1. def f(a, b):
   
2.     if a>b:
   
3.         t = a
   
4.         a = b
   
5.         b = t
   
6. 
   
7.     t = a
   
8.     while t%a|t%b:
   
9.         t += a
   
10.     return t
    
11. 
    
12. def main():
    
13.     COUNT = 20
    
14.     a = []
    
15.     for i in range(0, COUNT):
    
16.         a.append(i + 1)
    
17. 
    
18.     k = 1
    
19. 
    
20.     for i in range(0, COUNT):
    
21.         k = f(k, a[i])
    
22. 
    
23.     print("\n最小公倍数为：%d" % k)
    
24. 
    
25. if __name__ == "__main__":
    
26.     main()

复制代码

永恒的蓝色梦想

xuan1788 发表于 2020-7-23 09:25
感觉经典的最小公倍数辗除法和质数累加的原理由异曲同工之妙呀

辗除法：

辗转相除法应该是这样的吧：

1. def gcd(x: int, y: int) -> int:
   
2.     while y:
   
3.         x, y = y, x % y
   
4.         
   
5.     return x
   
6. 
   
7. 
   
8. def lcm(x: int, y: int) -> int:
   
9.     return x*y//gcd(x, y)

复制代码

xuan1788

永恒的蓝色梦想 发表于 2020-7-23 11:57
辗转相除法应该是这样的吧：

没错：
<while y:
x, y = y, x%y>

这种形式更符合辗除的字面意思，我的方法是从累加的角度得到辗除的结果，其实除法乘法在我看来，都可以用加减法做改写，当然，只是个人看法~

永恒的蓝色梦想

xuan1788 发表于 2020-7-23 13:29
没错：

然而效率太低了

yhhpf

1. a = 2520
   
2. flag = 1
   
3. while flag:
   
4.     a += 20
   
5.     for b in range(11,21):
   
6.         if a % b != 0 :
   
7.             break
   
8.         if b == 20:
   
9.             flag = 0
   
10. print(a)

复制代码

emmm/最直白方法。

4444567

1. from time import time
   
2. 
   
3. def beishu(x,y):
   
4.     if x > y:
   
5.         x,y = y,x
   
6.     for i in range(1,x*y):
   
7.         if y*i%x==0:
   
8.             return y*i
   
9. 
   
10. t1 = time()
    
11. n = int(input('请输入需要求的数字：'))
    
12. m = n
    
13. w =1
    
14. for i in range(1,m):
    
15.     w = beishu(w,i+1)
    
16.    
    
17. print('%d 是最小的能被 1-%d 中每个数字整除的正整数' % (w,m))
    
18. 
    
19. t2 = time()
    
20. t=t2-t1
    
21. print('耗时为：%s' % t)

复制代码