Project Euler #5 | can't understand solution

225 views Asked by At

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(divisible with no remainder) by all of the numbers from 1 to N?

Input Format : First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Output Format : Print the required answer for each test case.

Constraints : 1≤T≤10 1≤N≤40

full link to the question

Here is code whose results were accepted by hackerrank but i am having trouble understanding the solution.

Can anyone please explain this?

what does the line ans *= i / (ans % i) do? Rest of it i understood.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

bool check_if_prime(long n);

int main(void) {
    long t, n, i, ans = 1;
    std::cin >> t;
    while(t--){
        std::cin >> n;
        for(i = 2; i <= n; ++i){
            if(!check_if_prime(i)){
                if(ans % i)
                    ans *= i / (ans % i);
            }else
                ans *= i;
        }
        std::cout << ans << std::endl;
        ans = 1;
    }
    return 0;
}

bool check_if_prime(long n){
    if(n == 2)
        return true;
    for(long i = 2; i * i <= n; ++i){
        if(n % i == 0)
            return false;
    }
    return true;
}
1

There are 1 answers

0
glear14195 On BEST ANSWER

The above code does not give the right output for a number of test cases. For example:

    Output     N   Correct Answer
    232792560  19  232792560
    1059261584 23  5354228880
    1117182544 25  26771144400
    1886839328 27  80313433200

You might want to check out Pham Trung's answer on a similar question I asked.