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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第五题：能被1到20所有的数都整除的最小正数
211/3返回列表123下一页
查看: 4021  |  回复: 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的回帖

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的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 鼓励讨论！ 2011-05-13 21:13:19
引用回帖:
Originally posted by holmescn at 2011-05-12 16:45:10:
1. 为什么不用all，要用any呢？
2. 问题很简单啊，算法太粗暴了。

all需要测试全部能整除,2:20都会计算
~any只要有2:20任意一个不整除,就break,
只有在全部整除那个数时,才会2:20全部计算一次
应该会比all快,我实际测试也是~any快过all.
不过这是我的理解,math works没有相关说明

这个问题好像没有其他办法,哈哈,只能粗暴解决

[ Last edited by libralibra on 2011-5-12 at 19:21 ]
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
5楼2011-05-12 19:10:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

微尘、梦想

木虫 (知名作家)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励讨论！ 2011-05-13 21:13:39
CODE:
#include
#define n 30
static int a=1;
void fun(int i);
void main(void)
{
        int i;
        for(i=2;i<=n;i++)
                fun(i);
        printf("%d\n",a);
}
void fun(int i)
{
        int j,k=i,m=a;
        for(j=2;j         {
                if((m%j==0)&&(k%j==0))
                {
                        k/=j;
                        m/=j;
                        j--;
                }
        }
        a*=k;
}

有感于2楼的想法，改进了一下算法，求出了能被1到20所有的数的整除的最小的正数，其运算时间不到1秒，其结果是：232792560
说明：虽然静态全局变量并不提倡使用，但用在这里，恰到好处。
算法：能被前n个数整除的最小正数x，n+1除以x与n+1的公约数，得结果b，x乘b即是能被前n+1个数整除的最小正数

ps:不能求出能被1到30所有的数的整除的最小的正数，因为会产生数据溢出问题，最大只能求到22，但算法是正确的。

[ Last edited by 微尘、梦想 on 2011-5-13 at 07:56 ]
赞一下(2人) 回复此楼
任风云变幻，我笑对人生！
6楼2011-05-12 21:35:50
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

zzy870720z

荣誉版主 (文坛精英)

优秀版主优秀版主优秀版主优秀版主
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励讨论！ 2011-05-13 21:13:58
FORTRAN程序，20内的整数的话也不到1s
很长，有些麻烦

结果232792560

30以内2329089562800
CODE:
        PROGRAM MAIN
        IMPLICIT NONE
        INTEGER N,I,J,K,M,FLAG
        INTEGER(8) SUM
        DIMENSION K(10)
        DO I=1,10
        K(I)=1
        END DO
        READ(*,*)N
        J=1
        DO I=2,N
                CALL ZS(I,FLAG)
                IF(FLAG.EQ.1)THEN
                        K(J)=I
                        J=J+1
                END IF
        END DO       
        DO I=1,J-1
                CALL KN(K(I),N)
        END DO
        SUM=1
        DO I=1,J-1
                SUM=SUM*K(I)
        END DO
        WRITE(*,*)SUM
        END

C        判断质数，FLAG=1为质数，否则不为质数。
        INTEGER        FUNCTION ZS(II,FLAG)
        INTEGER II,I,J,K,FLAG
        K=INT(II/2)
        FLAG=1
        DO I=2,K
        IF(MOD(II,I).EQ.0)THEN
                FLAG=0
                GOTO 10
        END IF
        END DO
10        RETURN
        END

C        判断某个质数的n次方在规定范围以内
        INTEGER FUNCTION KN(X,N)
        IMPLICIT NONE
        INTEGER X,Y,N,SUM
        Y=1
        SUM=X
        DO WHILE(SUM.LT.N)
                SUM=SUM*X
                Y=Y+1
C        WRITE(*,*)X,N
        END DO
        X=SUM/X
        END

[ Last edited by zzy870720z on 2011-5-12 at 22:46 ]
赞一下(2人) 回复此楼
博学、审问、慎思、明辨、笃学
7楼2011-05-12 22:36:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★
余泽成(金币+3): 鼓励讨论！ 2011-05-13 21:14:16
微尘、梦想(程序强帖+1): 2011-05-14 19:29:31
OK,贴算法了！

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

算法说明：
求最小公倍数，当然就是把所有合数的质因子，去掉公因子，然后再乘起来就OK了。

下面给出三种语言的实现：

Matlab:
CODE:
clear;
tic;
primes  = [2 3 5 7 11 13 17 19];
factors = [];
numbers = 1:20;

for i = 1:length(primes)
    while any(mod(numbers, primes(i)) == 0)
        for j = 1:length(numbers)
            if mod(numbers(j), primes(i)) == 0
                numbers(j) = numbers(j) / primes(i);
            end
        end
        factors = [factors primes(i)];
    end
end

result = 1;
for i = 1:length(factors)
    result = result * factors(i);
end
disp(num2str(result));
toc;

Fortran:
CODE:
Program Euler5
    Implicit None
    Integer, Dimension(8) :: Primes
    Integer, Dimension(100) :: Factors
    Integer, Dimension(20)  :: Numbers
    Integer I, J, N
    Real(8) :: Res

    Primes = (/2, 3, 5, 7, 11, 13, 17, 19/)
    Numbers = (/(I, I=1, 20)/)
    N = 1

    Do I = 1, Size(Primes)
        Do While(Any(Mod(Numbers, Primes(I)) == 0))
            Do J = 1, Size(Numbers)
                If(Mod(Numbers(J), Primes(I)) == 0) Then
                    Numbers(J) = Numbers(J) / Primes(I)
                EndIF
            EndDo
            Factors(N) = Primes(I)
            N = N + 1
        EndDo
    EndDo

    Res = 1.0
    Do I = 1, N - 1
        Print '(I2)', Factors(I)
        Res = Res * Factors(I)
    EndDo

    Print '(F20.0)', Res

EndProgram Euler5

C:
CODE:
#include

int any(int Numbers[], int n, int Prime){
    int i;
    for(i = 0; i < n; i++){
        if(Numbers[i] % Prime == 0)
            return 1;
    }

    return 0;
}

int main(int argc, char** argv){
    int Primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
    int Factors[100];
    int Numbers[20];
    int sizeOfNumbers = sizeof(Numbers)/sizeof(int);
    int sizeOfPrimes  = sizeof(Primes)/sizeof(int);
    int i, j, n = 0;
    double result = 1;

    for(i = 0; i < sizeOfNumbers; i++) Numbers[i] = i + 1;

    for(i = 0; i < sizeOfPrimes; i++) {
        while(any(Numbers, sizeOfNumbers, Primes[i])) {
            for(j = 0; j < sizeOfNumbers; j++){
                if(Numbers[j] % Primes[i] == 0){
                    Numbers[j] /= Primes[i];
                }
            }
            Factors[n++] = Primes[i];
        }

    }

    for(i = 0; i < n; i++){
        result *= Factors[i];
    }
    printf("%18.0f\n", result);

    return 0;
}

当然我这里偷个个懒，就是直接给出了小于20的质数。不过，这个质数列表的生成也不难，参考Euler 工程 第三题的算法。

如果要给出N个数的最小公倍数。只要给个Numbers的列表就可以了。我想这个算法还是很实用的。

[ Last edited by holmescn on 2011-5-13 at 12:51 ]
赞一下(2人) 回复此楼
8楼2011-05-13 11:31:07
已阅   回复此楼   关注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的回帖

ming.su

银虫 (初入文坛)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 鼓励讨论！ 2011-05-13 21:14:52
tic;
result=2520*11*13*17*19*2;
toc;


Elapsed time is 0.002653 seconds.
赞一下(2人) 回复此楼
https://drwater.rcees.ac.cn
10楼2011-05-13 20:29:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
211/3返回列表123下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭