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

a315734685

代码不难, 算好久都没算出来,
如果是1-10的话, 还是可以秒出的.
x = 1
while 1:
    for i in range(1, 21):
        if x % i != 0:
            break
    else:
        print(x)   # 听说Python独有的, 循环顺利结束才会执行的语句块.
        break
    x += 1

# 大概五分钟左右跑出来的结果 232792560  

永恒的蓝色梦想

a315734685 发表于 2020-9-1 17:30
代码不难, 算好久都没算出来,
如果是1-10的话, 还是可以秒出的.
x = 1

嘿嘿，其实 else 块在 C/C++ 中是可以用 goto 实现的。

有马_冬巳

'''2520 是最小的能被 1-10 中每个数字整除的正整数。
最小的能被 1-20 中每个数整除的正整数是多少？'''

def prime(num):
    prime_seq = [3,5]
    for factor in range(3,num):
        check_prime = 0
        if 3 > int(factor/2):
            check_prime += 1
            pass
        else:
            for prime in range(2,int(factor/2)):
                if factor%prime == 0:
                    check_prime += 1
                    break
        if check_prime == 0:
            prime_seq.append(factor)
    global total
    total = 1
    for each in prime_seq:
        total *= each

def least_commonmultipler(num):
    prime(num)
    num = total
    while True:
        check = 0
        for i in range(1,21):
            if num%i != 0:
                check += 1
                num += total
                break
        if check == 0:
            print(num)
            break

start_least_common_multipler = time.time()
least_commonmultipler(20)
time_least_common_multipler = time.time() - start_least_common_multipler
print("%f秒" %time_least_common_multipler)

232792560
0.000496秒
改变least_commonmultipler后的参数可实现更大数字，速度奇快
原理就是吧范围内的质数找出后求积，再叠加求值

有马_冬巳

有马_冬巳 发表于 2020-10-2 16:07
232792560
0.000496秒
改变least_commonmultipler后的参数可实现更大数字，速度奇快

亲测求10万的时间是14秒

583164028

Range[20] // FactorInteger /@ # & // Flatten[#, 1] & // 
    DeleteDuplicates // GatherBy[#, First] & // Last /@ # & // 
 Times @@ Apply[Power, #, {1}] &
 (*代码的思路就是算出1-20所有整数分解因子，去重，排序，分组，取最大幂，构造出最终结果*)

gonorth

适用更大的数应该。
import math as m
def is_prime(n):
    if n > 1:
        if n == 2 :
            return True
        if n % 2 == 0:
            return False
        for each in range(3, int (m.sqrt(n)+1), 2):
            if n % each == 0:
                return False
        return True
    return False

def get_prime(n):
    while 1:
        if is_prime(n):
            yield n
        n = n + 1

def solve():
    count = 2
    for i in get_prime(3):
        if i < 21:
            count *= i

        else:
            count1 = count
            print('prime', count)
            list1 = list(range(2,21))
            while 1:
                a = 1
                for x in list1:
                    if count % x != 0:
                        a = 0
                        break
                if a:
                    print(count)
                    break
                count = count + count1
            return

solve()

a1351468657

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

牛逼！ 好想法

酷爱语言的小白

def numb_min(n):
    list1 = list(range(1,n+1))
    for i in range(n):
        for j  in range(i+1,n):
            if list1[j]% list1[i] == 0:
                list1[j] = int(list1[j]/list1[i])
    m = 1
    for k in list1:
        m = m* k
    return m
print(numb_min(20))

Kuri5u

#从质数往上推
num=base=19*17*11*13*2*3*5*7
lest=list(range(2,21))
flag=1
while 1:
    for each in lest:
        if num % each != 0:
            flag=0
            break
    if flag:
        print(num)
        break
    num+=base    

永恒的蓝色梦想

from math import lcm
from functools import reduce
print(reduce(lcm, range(1, 20 + 1)))

卢本伟牛逼

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

int count = 0;

int main1(void)//count = 648974546
{
        int i, result=1;
        int limit = 20, flag;
        
        //printf("上限:");
        //scanf("%d", &limit);
        
        while(1){
                for(i=1;i<=limit;i++)
                {
                        count += 1;
                        if(result%i != 0){
                                result += 1;
                                break;
                        }
                        if (i == limit){
                                flag = 1;
                        }
                }
                if (result % limit == 0 && flag){
                        break;
                }
        }
        printf("result = %d\n", result);
        printf("count = %d\n", count);
        return 0;
}

int is_prime(int value)
{
        int i;
        for(i=2;i<=sqrt(value);i++)
        {
                count += 1;
                if (i>3) i++;//step 1
                if (value % i == 0) return 0;
        }
        return 1;
}

int find_step(int value)// step 2
{
        int result = 1;
        int i,j;
        for(i=2;i<=value;i++)
        {
                count += 1;
                if (is_prime(i)){
                        result *= i;
                }
        }
        return result;
}

int is_multiply(int value, int limit)
{
        int i;
        for(i=1;i<=limit;i++)
        {
                count += 1;
                if (value%i!=0) return 0;
        }
        return 1;
}

int main(void) // count = 212
{
        int i = 1;
        int limit = 20;
        int step = find_step(limit);
        
        while(!is_multiply(step * i, limit)) i++;
        printf("result = %d\n", step * i);
        printf("count = %d\n", count);
}

鱼塘里的鱼儿

#include <iostream>
using namespace std;
int main()
{
        for(int i=20,j=0;;i++)
        {
         for(int i0=1;i0<=20;i0++)
         {
          if(i%i0!=0)
                 break;
          if(i0==20)
                {
                 cout<<i<<endl;
                  j=1;
            }
         }
         if(j==1)
            break;
        }
                return 0;
}
//我用C++写出来的答案：232792560

ft215378

#1-20 中能被每个数整除的正整数(即最小公倍数)
'''
两个数的乘积 = 最大公约数 * 最小公倍数
'''

#求两个数最大公约数
def gcd(n1,n2):
    if n2 > 0:
        return gcd(n2, n1 % n2)
    else:
        return n1


#求两个数最小公倍数
def lcm(n1,n2):
    return n1 * n2 // gcd(n1, n2)


num = 20 #求1多少num就写多少
#将每次求得的最小公倍数作为n1再与下一个数求最小公倍数
a = lcm(1, 2)
for i in range(3, num+1):
    a = lcm(a, i)

print(a)
               
   

番杰

#include<stdio.h>

int mian(void)
{
        int flag = 0 ;
        int result ;
        for(int i = 2520 ;;i++)
        {
                for(int j = 11;j < 21;j++)
                {
                        if(i / j == 0)
                        {
                                flag ++;
                        }
                        else
                                break;
                }
                if(flag  == 10)
                {
                        result = i ;
                        break;
                }
        }
        
        printf("%d",result);
        
        return 0； 
} 

learner-ray

最小能被1-20 中每个数整除的正整数是232792560

i初始

#include<stdio.h>

int main(void)
{
        int i, k, j;
        int count;
        i = k = 2*3*5*7*11*13*17*19;
        
        while (1)
        {
                count = 0;
                for (j = 1; j < 21; j++)
                {
                        if (i % j == 0)
                        {
                                count++;
                        }
                        else
                        {
                                break;
                        }
                }
                if (count == 20)
                {
                        printf("最小能被1-20 中每个数整除的正整数是%d\n", i);
                        break;
                }
                else
                {
                        i = i + k;
                }
        }
        return 0;
}

化为2*3*5*7*11*13*17*19是抄的评论大神的，我自己写的是i初始化为21，循环i++;运行了2秒多。大神的方法只运行了0.2秒。快了十倍。

guosl

暴力但平行编程，效果也不错。

/*
答案：232792560
耗时：2.82237秒（单线程）
      0.385815秒（八线程）
*/

#include <iostream>
#include <omp.h>
using namespace std;

const int nStep = 2000;
const long long INF = 0x7fffffffffffffLL;

inline bool chk(long long n)
{
  for (int i = 3; i < 20; ++i)
  {
    if ((n % i) != 0)
      return false;
  }
  return true;
}

int main(void)
{
  double t = omp_get_wtime();
  volatile long long N = 21;
  volatile bool bContinue = true;
  long long lResult = INF;
#pragma omp parallel shared(N, bContinue) reduction(min:lResult)
  while (bContinue)
  {
    long long k, lR;
#pragma omp critical
    {
      lR = lResult;
      k = N;
      N += nStep;
    }
    for (int i = k; i < k + nStep; ++i)
    {
      if (chk(i))
      {
        if (i < lR)
          lR = i;
        break;
      }
    }
    if (lR < lResult)
    {
#pragma omp critical
      {
        lResult = lR;
        bContinue = false;
      }
    }
  }
  t = omp_get_wtime() - t;
  cout << lResult << endl << t << endl;
  return 0;
}

mathtimes

long long LGCD(long long x,long long y)
{
    if(y == 0)
        return x;
    return LGCD(y,x%y);
}
long long LLCM(long long x,long long y)
{
    return x*y/LGCD(x,y);
}
long long LCMS(long long tot,int i)
{
    if(i>1)
        return LCMS(LLCM(tot,i),i-1);
    return tot;
}
#include <stdio.h>
int main()
{
    printf("%ld",LCMS(2,20));
}

mathtimes

from math import lcm
i = 1
for j in range(2,21):
    i = lcm(i,j)
print(i)

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毫秒都不用