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

python6 发表于 2018-12-19 16:29:40

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

这个FOR 要运行很久。

何小胖胖 发表于 2019-2-19 17:50:33

对于这个题，感觉可以由几种方面来减少运行时间，
第一就是要判断的数的选择，一个个往上加和一次加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;
}

王小召 发表于 2019-4-10 10:04:38

质子列表：
返回结果：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())

成为极客 发表于 2019-5-26 20:13:14

import time as t
start = t.perf_counter()
i = j = 11*13*17*19
list1 =
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

永恒的蓝色梦想 发表于 2019-8-3 10:33:36

本帖最后由永恒的蓝色梦想于 2020-7-23 15:14 编辑

Pythonfrom math import gcd
res = i = 1

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

print(res)

怀心抱素 发表于 2019-9-4 16:21:12

# 两个数的最大公约数
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 发表于 2019-10-9 08:28:10

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

}

就是要努力呀 发表于 2020-1-20 22:39:00

//!!!求能被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));//求1-20内每一个数的质因数

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

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

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

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

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

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

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

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

   return 0;
}

长大1/2 发表于 2020-1-25 16:43:20

#include <stdio.h>
#define NUM 20

int main(){
int num = NUM;
int i;
int array1;
int array2;
//初始化数组
for (i = 0;i<num;i++){
if (i == 0){
array1=1;
}else{
array1 = array1 + 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 = j;
}

}
//用短除法的方式求最小公倍数
long long result = 1;

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

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

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

return 0;
}

长大1/2 发表于 2020-1-25 16:43:54

#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 发表于 2020-3-12 18:28:20

很多欧拉计划中解题方法都可以用质数来求解
感觉最简单的算法，速度应该是最快的
10: 2520
20:answer:232792560
30:answer:2329089562800
40:answer:5342931457063200
typedef long long ElementType;
void getMinNumberOfFlag( ElementType *answer, int flag)
{
int array = {0};
int temp = {0};
int prime = {0};

prime = 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 == 0)
         {
            temp-1] += 1;
            value /= prime;
            yes = false;
         }
         if(value > prime)
         {
            k++;
         }else
         {
            break;
         }
   }
   if(yes)
   {
         prime = value;
         temp = 1;
   }

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

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

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

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

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

永恒的蓝色梦想 发表于 2020-4-20 15:17:49

本帖最后由永恒的蓝色梦想于 2020-7-23 15:19 编辑

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

永恒的蓝色梦想 发表于 2020-4-20 15:18:32

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

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

leon0149 发表于 2020-5-7 14:43:12

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 发表于 2020-7-23 09:25:06

本帖最后由 xuan1788 于 2020-7-23 09:38 编辑

牡丹花下死做鬼发表于 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)

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

if __name__ == "__main__":
main()

永恒的蓝色梦想 发表于 2020-7-23 11:57:43

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 13:29:02

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

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

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

永恒的蓝色梦想 发表于 2020-7-23 13:33:09

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

然而效率太低了

yhhpf 发表于 2020-8-24 13:27:11

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 发表于 2020-8-30 20:49:51

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)

页: 1 2 3 [4] 5 6

鱼C论坛's Archiver