Thread: Find a number that's divided equally by a specified range of numbers

Code:

/* 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 the numbers from 1 to 20? */


#include <stdio.h>


int main (void)
{
	int i, j, k;


	for (i = 1; i < 9999; i++)
	{
		for(j = 1; j < 10; j++)
		{	
			if (i % j == 0)
			{
				printf("%d,%d = %d\n", i, j, i%j);
			}
		}
	}


	return 0;
}

hey all, i've made an honest attempt at this programming question. First of all I am guessing it is correct do use a nested for loop. Mainly my question, with the if statement, i can see with the printf function after running the program with the 'j' variable which ones are matching with with results between 1 through 10. However, I don't know how to do have the second for loop (j = 1) line do this with a followup if statements. I believe the code I found would be similar to this nested loops in C - Tutorialspointlink, i tried using this as a reference but wasn't successful. I'm stumped. Thanks.

Originally Posted by john.c

Naive method:

Code:

#include <stdio.h>
 
int main()
{
    for (int n = 1; ; n++)
    {
        int d = 1;
        for( ; d < 21; d++)
            if (n % d != 0)
                break;
        if (d == 21)
        {
            printf("%d\n", n);
            break;
        }
    }
    return 0;
}

Faster method:

Code:

#include <stdio.h>
 
void find_divs(int n, int *divs)
{
    for (int d = 2; d <= n; ++d)
    {
        int cnt = 0;
        while (n % d == 0)
        {
            n /= d;
            ++cnt;
        }
        if (divs[d] < cnt)
            divs[d] = cnt;
    }
}
  
int main()
{
    int divs[20] = {0};
    for (int d = 1; d <= 20; ++d)
        find_divs(d, divs);
    int n = 1;
    for (int d = 1; d < 20; ++d)
        for (int i = 0; i < divs[d]; ++i)
            n *= d;
    printf("%d\n", n);
    return 0;
}

thanks for your time john.c responding to my question

Code:

#include <stdio.h>

Code:

int main()
{
    for (int n = 1; ; n++)
    {
        int d = 1;
        for( ; d < 21; d++)
            if (n % d != 0)
                break;
        if (d == 21)
        {
            printf("%d\n", n);
            break;
        }
    }
    return 0;
}

you can view the Nest loop c - Adzetech tutorials for better understanding.

Originally Posted by Zeus_

This is a Project Euler problem that I too solved a few days back.
Here's my solution: Competetive-Programming-Q-A/#5 Smallest Multiple.cpp at master * ZeusNoTZues/Competetive-Programming-Q-A * GitHub

Code:

int main ()
{
      unsigned long long N, LCM = 1;

      cin >> N; // 20

      for (ull i = 2; i <= N; i++)
            LCM = LCM * i / __gcd (LCM, i);

      cout << LCM;

      return 0;
}

I like how john explained the two different approaches.

And I like your solution (a lot)

I probably wouldn't have used __gcd() but only because it's non-standard (although if your code is C++ there is always std::gcd() for c++17 or later). Other than that it's a lot nicer than my implementation

Originally Posted by Zeus_

Thanks! I've didn't know std::gcd() and std::lcm() were added in C++17. I'll use them from now on. Although, even when I compiled using -std=c++1z, I get the error of gcd not being declared in the scope. Is it because my mingw stl version is older? Or am I doing something else wrong?

I'm not sure why it wouldn't work. Maybe the mingw version is the problem... dunno sorry

Code:

#include <numeric>
#include <iostream>

int main () {
    int a = std::gcd(15,5);
    std::cout << a << '\n';
    return 0;
}

$ g++ --version
g++ (GCC) 9.2.1 20190827
$ g++ --std=c++17 -Wall -Wextra test.cpp 
$ ./a.out 
5
$ g++ --std=c++1z -Wall -Wextra test.cpp   # works as well