题目5：找出最小的能被1-20中每个数整除的数,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

a315734685 发表于 2020-9-1 17:30:24

本帖最后由 a315734685 于 2020-9-1 17:33 编辑

代码不难, 算好久都没算出来,
如果是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

永恒的蓝色梦想 发表于 2020-9-1 21:21:16

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

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

有马_冬巳 发表于 2020-10-2 16:07:01

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

def prime(num):
prime_seq =
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:09:05

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

亲测求10万的时间是14秒

583164028 发表于 2020-11-4 09:45:30

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

gonorth 发表于 2020-11-4 23:32:17

适用更大的数应该。
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 发表于 2021-3-6 13:40:41

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

牛逼！好想法

酷爱语言的小白 发表于 2021-4-26 15:28:10

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

Kuri5u 发表于 2021-5-4 11:25:16

#从质数往上推
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

永恒的蓝色梦想 发表于 2021-6-23 07:42:18

本帖最后由永恒的蓝色梦想于 2021-8-27 11:11 编辑

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

卢本伟牛逼 发表于 2021-8-9 00:15:42

#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);
}

鱼塘里的鱼儿 发表于 2021-10-6 09:44:38

#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 发表于 2021-10-9 12:49:10

#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)

番杰发表于 2021-10-27 13:56:20

本帖最后由番杰于 2021-10-27 14:06 编辑

#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 发表于 2021-11-13 02:45:00

最小能被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 发表于 2022-1-2 11:46:23

暴力但平行编程，效果也不错。
/*
答案：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 发表于 2022-1-28 15:03:51

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 发表于 2022-2-12 10:59:11

本帖最后由 mathtimes 于 2022-2-12 11:07 编辑

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

Kazimierz 发表于 2022-2-22 12:02:31

大概跑了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 发表于 2022-2-23 08:37:59

用“动态规划”的思想求解，其实很方便。
要求的数需要被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毫秒都不用{:5_109:}

页: 1 2 3 4 [5] 6

鱼C论坛's Archiver