应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第五题：能被1到20所有的数都整除的最小正数
51/1返回列表
查看: 4514  |  回复: 20
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 6 个 程序强帖 ，点击这里进行查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

holmescn

金虫 (正式写手)

[交流] Euler 工程 第五题：能被1到20所有的数都整除的最小正数 已有11人参与

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

2520是一个能被1到10中的每个数都除尽的最小的数。
那么能被1到20所有的数的整除的最小的正数是多少呢？
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2011-05-12 15:03:50
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励讨论！ 2011-05-13 21:14:37
引用回帖:
Originally posted by holmescn at 2011-05-13 11:31:07:
OK,贴算法了！

本题其实在数学上很简单，能被1到20所有的数都整除的最小正数，当然就是1到20这20个数的最小公倍数。所以用最小公倍数算法就最简单了。关于最小公倍数算法，请自行看书或查维基百科。

算法说 ...

我觉得三层循环还是多了，两层循环就可以
第一步是分离数表，将质数和非质数分离，质数不超过lgn个，所以可以在O(lgn)时间内解决
第二步是从质数表中，进行叠乘运算，找出所能叠到的最大值。这么做的原因是，质数代表了所有的公因子，而公倍数包含公因子的乘方，这个循环也可以在O(lgn)的时间上限完成。
下面是手算演示：
1-10的素数表： 2，3，5，7
叠乘：2*2*2=8，到达临界条件，取得4，
3*3=9，到达临界条件，取得3
最终叠乘：2*3*5*7*3*4=2520
----------------------------------------------------------------
1-20的素数表：2，3，5，7，11，13，17，19
叠乘：2*2*2*2=16，剔除2取得8
3*3=9，到达临街条件，取得3
最终叠乘：2*3*5*7*11*13*17*19*3*8=232792560
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
9楼2011-05-13 19:58:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 21 个回答

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3): 鼓励交流！ 2011-05-12 19:11:36
余泽成(程序强帖+1): 2011-05-12 19:12:13
CODE:
%% evenly divided by 1:20
% Elapsed time is 173.211097 seconds.
% ans =
%    232792560
function result = euler5()
tic;
flag = 0;
result = 2520; % 能被1-20整除,肯定比能被1-10整除的2520大
while flag==0
    result = result+10; % 能被10整除,所以每次增加10
    flag = ~any(mod(result,2:20)); % 检测2-20,如果全部可以整除,改变flag结束循环
end
toc;
end

效率有点低,170多秒啊,
赞一下(3人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
2楼2011-05-12 16:36:07
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
引用回帖:
Originally posted by libralibra at 2011-05-12 16:36:07:
[code] %% evenly divided by 1:20
% Elapsed time is 173.211097 seconds.
% ans =
%    232792560
function result = euler5()
tic;
flag = 0;
result = 2520; % 能被1-20整除,肯定比能被1-10整除的2520 ...

1. 为什么不用all，要用any呢？
2. 问题很简单啊，算法太粗暴了。
赞一下 回复此楼
3楼2011-05-12 16:45:10
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

微尘、梦想

木虫 (知名作家)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 谢谢参与交流！ 2011-05-12 19:12:02
CODE:
#include
#include
int x(int i);
void main(void)
{
        int i;
        float dif;
        time_t start,end;

        time(&start);
        for(i=1;1;i++)
                if(x(i))
                {
                        printf("%d\n",i);
                        break;
                }
        time(&end);
        dif=difftime(end,start);
        printf("运算时间：%.1f秒\n",dif);
}
int x(int i)
{
        int j,k=0;
        for(j=2;j<21;j++)
                if(i%j==0)
                        k++;
        if(k==19)
                return 1;
        else return 0;
}

答案：232792560
运行时间：37s

算法：最笨的那种！

[ Last edited by 微尘、梦想 on 2011-5-12 at 17:20 ]
赞一下(2人) 回复此楼
任风云变幻，我笑对人生！
4楼2011-05-12 17:19:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 21 个回答
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 关于filecode，很负责任的告诉大家 +4 爱看书的可乐 2026-08-08 5/250 2026-08-08 19:06 by 超级海虾
[基金申请] 国基金的申报应该改成非等额制，评价高的钱多评价低的钱少，但是增加资助率 +7 a089 2026-08-07 7/350 2026-08-08 18:05 by gltch
[公派出国] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +3 qTvzQBRAHjCi 2026-08-07 4/200 2026-08-08 17:27 by oEVWOejN9taj
[考研] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +3 qTvzQBRAHjCi 2026-08-07 5/250 2026-08-08 16:47 by oEVWOejN9taj
[基金申请] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 Vi50GxzrFcSG 2026-08-07 5/250 2026-08-08 16:27 by oEVWOejN9taj
[论文投稿] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 WQyTGMbfH7Cx 2026-08-07 4/200 2026-08-08 15:02 by oEVWOejN9taj
[博后之家] 售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急 +3 HEQlVqMTIA7d 2026-08-07 6/300 2026-08-08 14:42 by oEVWOejN9taj
[公派出国] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +3 HEQlVqMTIA7d 2026-08-07 6/300 2026-08-08 14:39 by oEVWOejN9taj
[教师之家] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +4 HEQlVqMTIA7d 2026-08-07 5/250 2026-08-08 14:27 by oEVWOejN9taj
[基金申请] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 HEQlVqMTIA7d 2026-08-07 4/200 2026-08-08 14:27 by oEVWOejN9taj
[基金申请] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +4 KXLV3nuBVBY7 2026-08-07 5/250 2026-08-08 14:07 by oEVWOejN9taj
[基金申请] 关于代码变化问题，想知道的进来 +11 且听虎啸 2026-08-07 14/700 2026-08-08 12:50 by 布布和一二
[考博] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 HEQlVqMTIA7d 2026-08-07 3/150 2026-08-08 03:47 by 6vVgjDL4CnGu
[基金申请] 基金中了 +14 laoda193707 2026-08-06 14/700 2026-08-08 00:23 by 实验小白ha
[基金申请] 娱乐 +6 Tide man 2026-08-03 6/300 2026-08-07 22:40 by 铁帽子农民
[基金申请] 固定端突然变了，今天 +6 archvillain 2026-08-06 10/500 2026-08-07 16:03 by 医学老男孩
[基金申请] 大家散了吧，后缀研究没有意义，别浪费时间了，过好目前的每一天，不要焦虑 +5 Tide man 2026-08-06 7/350 2026-08-07 13:11 by 医学老男孩
[基金申请] filecode +14 等待解的谜 2026-08-06 19/950 2026-08-07 12:20 by wlwhappy
[基金申请] 求各位大神看下 100+6 hpkpkpkp 2026-08-05 33/1650 2026-08-06 14:49 by zhiyanjiang
[基金申请] 有没有H口的？有收到消息的吗？ +3 超级海虾 2026-08-04 3/150 2026-08-04 17:26 by 学教育滴
信息提示
关闭
请填处理意见
关闭