题目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())

成为极客

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

232792560
0.0015221600000000016

永恒的蓝色梦想

Python

from math import gcd
res = i = 1

while i <= 20:
    res *= i // gcd(res, i)
    i += 1

print(res)

怀心抱素

# 两个数的最大公约数
def func(a, b):
    if a == 0:
        return b
    else:
        if b > a:
            a, b = b, a
        a = a % b
        return func(a, b)

# 两个数的最小公倍数
def func1(a, b):
    return a * b / func(a, b)

# 一个区间的最小公倍数
def func2(a=1, b=20):
    c = 1
    for a in range(a, b+1):
        c = func1(a, c)
    return c

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

typedef long long ElementType;
void getMinNumberOfFlag( ElementType *answer, int flag)
{
    int array[flag] = {0};
    int temp[flag] = {0};
    int prime[flag] = {0};

    prime[0] = 2;
    int i = 1;
    int j = 2;
    int k = 0;
    bool yes = true;
    int value = j;

    while(true)
    {
        if(value > flag)
        {
            break;
        }
        k = 0;
        while( k < i)
        {
            while(value % prime[k] == 0)
            {
                temp[prime[k]-1] += 1;
                value /= prime[k];
                yes = false;
            }
            if(value > prime[k])
            {
                k++;
            }else
            {
                break;
            }
        }
        if(yes)
        {
            prime[i++] = value;
            temp[value-1] = 1;
        }

        for(int my = 0; my < flag; my++)
        {
            if(array[my] < temp[my])
            {
                array[my] = temp[my];
            }
            temp[my] = 0;
        }

        j += 1;
        value = j;
        yes = true;
    }

    for(j = 0; j < i; j++)
    {
        printf("%d\n",prime[j]);
    }

    printf("\n");
    *answer = 1;
    for(j = 0; j < flag; j++)
    {
        printf("%d\n", array[j]);
        *answer *= (int) pow(j+1, array[j]);
    }
}

int main(int argc, char *argv[])
{
    ElementType  ret;
    getMinNumberOfFlag(&ret, 30);
    printf("answer:%d\n",ret);
    return 0;
}

永恒的蓝色梦想

C++ 0ms

#include<iostream>
using namespace std;



int main() {
    ios::sync_with_stdio(false);

    unsigned x, y, temp, i, result = 1;


    for (i = 1; i <= 20; ++i) {
        x = result;
        y = i;

        while (y) {
            temp = x % y;
            x = y;
            y = temp;
        }

        result *= i / x;
    }


    cout << result << endl;
    return 0;
}

永恒的蓝色梦想

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

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

leon0149

def isOK(x):
    for i in range(1, 21):
        if x % i:
            return False
    else:
        return True


num = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19
i = num
while True:
    if isOK(i):
        break
    i += num

print(i)

xuan1788

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

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

辗除法：

def f(a, b):
    if a>b:
        t = a
        a = b
        b = t

    t = a
    while t%a|t%b:
        t += a
    return t

def main():
    COUNT = 20
    a = []
    for i in range(0, COUNT):
        a.append(i + 1)

    k = 1

    for i in range(0, COUNT):
        k = f(k, a[i])

    print("\n最小公倍数为：%d" % k)

if __name__ == "__main__":
    main()

永恒的蓝色梦想

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

辗除法：

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

def gcd(x: int, y: int) -> int:
    while y:
        x, y = y, x % y
        
    return x


def lcm(x: int, y: int) -> int:
    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

a = 2520
flag = 1
while flag:
    a += 20
    for b in range(11,21):
        if a % b != 0 :
            break
        if b == 20:
            flag = 0
print(a)

emmm/最直白方法。

4444567

from time import time

def beishu(x,y):
    if x > y:
        x,y = y,x
    for i in range(1,x*y):
        if y*i%x==0:
            return y*i

t1 = time()
n = int(input('请输入需要求的数字：'))
m = n
w =1
for i in range(1,m):
    w = beishu(w,i+1)
    
print('%d 是最小的能被 1-%d 中每个数字整除的正整数' % (w,m))

t2 = time()
t=t2-t1
print('耗时为：%s' % t)