返回顶部

收藏

求一列数的最小公倍数

更多

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之间的每个数字整除的最小整数是多少?

void swith_param_order(int *a, int *b)
{
    int tmp;
    if(a<b)
    {
        tmp=a;
        a=b;
        b=tmp;
    }
}

int max_common_divisor(int a, int b)
{
    int r;
    int divisor;
    swith_param_order(&a,&b);
    r=a%b;
    if(r==0)
    {
        divisor=b;
    }
    else
    {
        divisor=max_common_divisor(b,r);
    }
    return divisor;
}

int smallest_multiple(int num)
{
    int i;
    int result=1;
    for(i=1;i<=num;i++)
    {
        if(result%i==0)
        {
            continue;
        }
        else
        {
           //calculate the smallest multiple of result and i
            result=(result*i)/max_common_divisor(result,i);
        }
    }
    return result;
}

void TestSmallestMultiple()
{
    int num=20;
    printf("Smallest Multiple:%d\\n",smallest_multiple(num));
}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

发表评论