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

  1. #1
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    112

    Angry 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. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    950
    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;
    }
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  3. #3
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    112
    Quote Originally Posted by john.c View Post
    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. #4
    null pointer Structure's Avatar
    Join Date
    May 2019
    Posts
    269
    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;
    }
    Last edited by Structure; 02-02-2020 at 03:55 PM.
    "without goto we would be wtf'd"

  5. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    950
    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
    If you want the truth to stand clear before you, never be for or against. - Sent-ts'an

  6. #6
    Registered User
    Join Date
    Feb 2020
    Posts
    1
    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. #7
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    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.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  8. #8
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,763
    Quote Originally Posted by Zeus_ View Post
    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. #9
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    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?
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  10. #10
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,763
    Quote Originally Posted by Zeus_ View Post
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. program to find largest number from given numbers
    By abhi143 in forum C Programming
    Replies: 3
    Last Post: 10-13-2019, 05:15 AM
  2. Random numbers are not in specified range
    By Cjof in forum C++ Programming
    Replies: 2
    Last Post: 11-10-2014, 12:58 PM
  3. program to find the range and average
    By narendrav in forum C Programming
    Replies: 7
    Last Post: 06-10-2011, 12:20 AM
  4. Find the number of even numbers on even positions
    By teodorrupi in forum C++ Programming
    Replies: 5
    Last Post: 02-27-2011, 11:37 AM
  5. Random Numbers within a range OTHER than 1-X
    By Kaelin in forum C++ Programming
    Replies: 11
    Last Post: 02-16-2005, 11:57 AM

Tags for this Thread