Problem5-Project Euler

Smallest multiple

 

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?

考虑质因数分解，将1-20都分解，挑质因数的最高幂次相乘即可。

#include"stdio.h"
#include"math.h"

#define N 20

int prime[N+1];

int find_prime(int x)
{
    int i,j,sum=1;
    for(i=1;i<=x;i++)
    {
        prime[i]=1;
        for(j=2;j<=int(sqrt(i));j++)
            if(i%j==0)
                prime[i]=0;
        if(prime[i]!=0&&i>=2)
        {
            prime[i]=int(log(x)/log(i));
            sum *= int(pow(i,prime[i]));
        }
    }
    return(sum);
}

int main()        /*problem5-smallest multiple*/
{
    printf("answer is %d
",find_prime(N));
    return(0);
}