CODEWITHSUNDEEP
javaalgorithmloops
Gl0deanR
Gl0deanR

Reputation: 27

How do I find the first number that divides with the first 20 numbers?

I want to find the smallest number that can be divided with no reminder(perfect division) by the first 20 numbers (1, 2, 3... 20).

I've tried something that I thought would not fail, that goes like this:

for (int i = 20; i < Integer.MAX_VALUE; i++) {
    int seImparte = 0;
    for (int j = 1; j <= 20; j++) {
        if (i % j != 0) {
            seImparte++;
        }
    }
    if (seImparte == 0) {
        System.out.println(i);
        break;
    }
}

I thought I would get the first number and then the program would exit, but it runs and nothing happens.

Thank you for your time and help!

Upvotes: 0

Views: 303

Answers (3)

MBo
MBo

Reputation: 80325

Instead of optimizing of brute-force approach, it is worth to use simple math rules.

Resulting complexity is O(n*log(n)) against "huge count"

Python code uses Least common multiple function

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)     # integer division


d = 1
for i in range(2, 21): #last i=20
    d = lcm(d, i)

print(d)

>>[Dbg]>>> 232792560

Also we can make factorization of all numbers in range into primes and remember the largest powers for every prime. In this case: 2:4; 3:2; 5:1; 7:1; 11:1; 13:1; 17:1; 19:1 and multiply these powers. More complex code (but this way might be useful sometimes)

232792560 = 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19

Upvotes: 2

Manasi
Manasi

Reputation: 765

@raulGLD Your code works fine but it is not optimezed,

You can break inner loop, after invalid condition
Also you can start from 3 or 7 as [1,2,3,4,5,6 can be tested by [4,6,8,10,12]
-This is optional but break is important

     for (int i = 20; i < Integer.MAX_VALUE; i++) {
      int seImparte = 0;
        for (int j = 7; j <= 20; j++) {
            if (i % j != 0) {
                seImparte++; break;
            }
        }
        if (seImparte == 0) {
            System.out.println(i);
            break;
        }
    }

output : 232792560

Upvotes: 2

Sudha Velan
Sudha Velan

Reputation: 633

Hope this is what you are looking:

for (int i = 2; i < Integer.MAX_VALUE; i++) {
        for (int j = 2; j <= 20; j++) {
            if (i % j == 0) {
                System.out.println("i : "+i+" j : "+j);
                break;
            }
        }
    }

Upvotes: 0

Related Questions