-4

There is no problem when I input a number smaller than 12 but when I input something bigger the code returns with no output without any error. What's the problem?

Sample output I am getting -

Sample 1 -

1 13
Press any key to continue....

Sample 2 -

1 12
27720
Press any key to continue....

Sample 3 -

1 10
2520
Press any key to continue....

More Information - Actually this is an Question from project Euler's Hackerrank Contest - Project Euler #5 - 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(divisible with no remainder) by all of the numbers from 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.

Constraints -

1 <= T <= 10
1 <= N <= 40

Output Format

Print the required answer for each test case.

Sample Input 0

2
3
10

Sample Output 0

6
2520

Here is my solution -

#include <bits/stdc++.h>

using namespace std;

long smallest_multiple(int n, long num){
    for(int i = 1; i <= n; i++){
        if(num % i != 0){
            while(num % i != 0){
                num++;
                return smallest_multiple(n, num);
            }
        }
    }
    return num;
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        long num = 2;
        long int ans = smallest_multiple(n, num);
        cout << ans << endl;
    }
    return 0;
}

Can you tell me what's going wrong and what can be done? P.S. Noob here, Please explain step by step. I'm just starting out.

Clifford
  • 88,407
  • 13
  • 85
  • 165
Shreyas Chavhan
  • 35
  • 5
  • What debugging have you tried ? – John3136 Nov 30 '20 at 08:31
  • 5
    `what's going wrong` The depth of the recursion is equal to the end result. That grows quickly, and you are overflowing the stack. `what can be done` Find a better algorithm, or at least change the recursion to a loop. – dxiv Nov 30 '20 at 08:37
  • Your loop body is equivalent to `if (num % i != 0) return smallest_multiple(n, num+1);`. – molbdnilo Nov 30 '20 at 08:40
  • 2
    see [Why should I not #include ?](https://stackoverflow.com/q/31816095/995714), [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/995714) – phuclv Nov 30 '20 at 08:48
  • 3
    An efficient solution consists in considering prime numbers p[i] less or equal to N, and then to calculate the power associated to each prime. For example, for N = 13, `num = 2^3 * 3^2 * 5 * 7 * 11 * 13;` – Damien Nov 30 '20 at 08:48
  • 2
    Project Euler problems can only rarely be solved using brute force algorithms. (That description does not look like it is from the Project Euler site, though.) – molbdnilo Nov 30 '20 at 08:51
  • 7
    Please post outputs as text, not screenshots – Alan Birtles Nov 30 '20 at 08:52
  • It could work with a bigger data type but I don't know if it will be proccessed. – just a guy Nov 30 '20 at 11:35

1 Answers1

-2

  • What was going wrong - The data was growing so quickly because of recursion, that it was overflowing the stack.

  • What I did -

Found a better algorithm that's not using recursion -

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        long n;
        cin >> n;
        long div = 2;

        while(div <= sqrt(n)){
            if(n % div == 0){
                n  /= div;
            }
            else{
                div++;
            }
        }

        cout << n << endl;

    }
    return 0;
}
Shreyas Chavhan
  • 35
  • 5