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

1. 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.

2. 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;
}```

3. 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

4. Code:
```#include <stdio.h>

int main(void) {

int i, j, k;

for ( i = 1; i < 9999; i++ ) {

k = 0;

for ( j = 1; j <= 10; j++ ) {

if ( (i % j) == 0 ) k++;

}

if ( k == 10 ) printf( "%i.", i );
}

return 0;
}```

5. You're welcome.

Note that the fast method first creates a list of the maximum number of times each prime factor appears in the numbers from 2 to 20. (I should've started the d loop in main at 2, but it doesn't hurt to start it at 1.)

The list is (leaving out factors that don't appear at all):
Code:
``` 2:  4
3:  2
5:  1
7:  1
11:  1
13:  1
17:  1
19:  1```
So the answer is (using Python's exponentiation notation **):
2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560

6. 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.

7. 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.

8. 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

9. 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?

10. 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```