Trying 3 different ways to do the same thing, each one is wrong

**shemer77** · May 30th, 2010, 06:52 PM

Here is what I am trying to do
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Here are my 3 different sets of code, the first 2 I know are definatly wrong, and I am just wondering how i would change them to be correct, but the third one I dont understand why it is wrong

public class Main {
    private static String result;
        public static void main( String argv[] )   {
                int count = 7;
                if (count % 1 == 0 && count % 2 == 0 && count % 3 == 0 && count % 4 == 0 && count % 5 == 0 && count % 6 == 0 && count % 7 == 0 && count % 8 == 0 && count % 9 == 0 && count % 10 == 0 && count % 11 == 0 && count % 12 == 0 && count % 13 == 0 && count % 14 == 0 && count % 15 == 0 && count % 16 == 0 && count % 17 == 0 && count % 18 == 0 && count % 19 == 0 && count % 20 == 0){
                   System.out.println("result" + result);
                } else {
                    System.out.println("wrong");
                    int++;
                }
        }
}

public class Main {
    private static String result;
        public static void main( String argv[] )   {
                int count = 7;
                inner :
                count++;
                if (count % 1 == 0 && count % 2 == 0 && count % 3 == 0 && count % 4 == 0 && count % 5 == 0 && count % 6 == 0 && count % 7 == 0 && count % 8 == 0 && count % 9 == 0 && count % 10 == 0 && count % 11 == 0 && count % 12 == 0 && count % 13 == 0 && count % 14 == 0 && count % 15 == 0 && count % 16 == 0 && count % 17 == 0 && count % 18 == 0 && count % 19 == 0 && count % 20 == 0){
                   System.out.println("result" + result);
                } else {
                   count++;
                   continue inner;
                }
        }
}

public class Main {
 
	public static void main(String[] args) {
		System.out.println("Calcluate this mofo");
		for (int count = 1; count % 1 == 0 && count % 2 == 0 && count % 3 == 0 && count % 4 == 0 && count % 5 == 0 && count % 6 == 0 && count % 7 == 0 && count % 8 == 0 && count % 9 == 0 && count % 10 == 0 && count % 11 == 0 && count % 12 == 0 && count % 13 == 0 && count % 14 == 0 && count % 15 == 0 && count % 16 == 0 && count % 17 == 0 && count % 18 == 0 && count % 19 == 0 && count % 20 == 0; count++) {
			System.out.println(count);
		}
	}
}

**Norm** · May 30th, 2010, 08:48 PM

Can you explain the algorithm(s) that you want to use?

why it is wrong

Can you explain a bit more? Or show the output and explain why its wrong.

**helloworld922** · May 30th, 2010, 09:51 PM

The smallest number divisible by a set of numbers is the smallest set of common prime factors.

So, you just need a list of prime factors for each number and then compute the smallest set that contains at least every factor in each of the sub-lists.

ex.:

(note: you can just ignore 1 since it plays no role essentially)

number     prime factors
1               NA
2               2
3               3
4               2, 2
5               5
6               2, 3
7               7
8               2, 2, 2
9               3, 3
10             2, 5
11             11
12             2, 2, 3
13             13
14             2, 7
15             3, 5
16             2, 2, 2, 2
17             17
18             2, 3, 3
19             19
20             2, 2, 5

So, the smallest common list needs at least 2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 17, and 19. Now, just multiply back and we get 232792560

Now, to compute prime factors of a number:

// pseudo-code
primeFactors(num):
    currPrime = 2
    factorsList = new list()
    while(num > 1):
        if(num % currPrime == 0):
            factorsList.add(currPrime)
            num = num / currPrime
        else:
            // you'll need to figure out a way to implement this function, either by calculating it or storing a list
            currPrime = nextPrime()
    return factorsList

edit:

what's wrong with your third piece of code:

What your saying is that while your current number is divisible by the number 1 through 20, check the next number. Your logic is exactly backwards. What it should be is while your number is not divisible by any number 1 through 20, increase the count.

**Norm** · May 31st, 2010, 09:16 AM

Another comment on the code: Its hardcoded to solve the problem for 20.
Try to write the code so it will solve the problem for any number x.

@hellowordl922
Could you explain how you get these numbers?
the smallest common list needs at least 2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 17, and 19.
Given the prime factors list
Thanks,

**shemer77** · May 31st, 2010, 10:48 AM

Originally Posted by helloworld922

edit:

what's wrong with your third piece of code:

What your saying is that while your current number is divisible by the number 1 through 20, check the next number. Your logic is exactly backwards. What it should be is while your number is not divisible by any number 1 through 20, increase the count.

Sorry I dont see that, I looked up the defintion of a for statement

Programmers often refer to it as the "for loop" because of the way in which it repeatedly loops until a particular condition is satisfied.

so my beggning is my integer, my end is when it is divisible by all those numbers,and if its not then add 1.

**Norm** · May 31st, 2010, 01:09 PM

Better re-read definition of the for loop conditioni part. The loop continues if the condition is true.
Your huge && condition tests true when? and false when?

**helloworld922** · May 31st, 2010, 02:58 PM

Are you familiar with set theory, Norm?

Basically, what I'm saying is that any set of prime factors is a subset of that main set A = {2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 17, 19}

So, if you take the set {2} (which represents the prime factors of 2), that's a subset of A, {2,2} is a subset of A (which represents the prime factors of 4), etc. etc.

This is an easy way to determine what the minimal number of factors needed is because it gets rid of all unnecessary factors. Let's take a smaller example, say the smallest number divisible by 2, 4, 8, and 16.

If we just multiplied each of these numbers out, we would obviously get too many 2's:
(prime factorization in parenthesis)
(2) * (2 * 2) * (2 * 2 * 2) * (2 * 2 * 2 * 2)

However, if we take the smallest set such that all prime factors are subsets of this main set, we would get {2,2,2,2}, or 16. Note: a set can be defined as a subset of itself, thus allowing us to say that {2,2,2,2} (the number 16) is a subset of {2,2,2,2} (again, the number 16), and therefore 16 divides 16 evenly, which makes perfect sense.

final note (probably the most important):

I'm kind of abusing set theory a little bit here, since technically in set theory you define one of each element in the set. So, {2, 2, 2, 2} in true set theory is actually just {2}. However, this distinction is vital in this analysis since otherwise we would say that 2 is divisible by 16, which is obviously not true.

**Norm** · May 31st, 2010, 03:00 PM

Thanks for the reply. Its been a long time since college and set theory.

**shemer77** · May 31st, 2010, 03:02 PM

it tests true when count is divisible by all the numbers from 1-20, it tests false when its not so i change it to this it still dosent work

public class Main {
 
	public static void main(String[] args) {
		System.out.println("Calcluate this mofo");
		for (int count = 57; count % 1 != 0 && count % 2 != 0 && count % 3 != 0 && count % 4 != 0 && count % 5 != 0 && count % 6 != 0 && count % 7 != 0 && count % 8 != 0 && count % 9 != 0 && count % 10 != 0 && count % 11 != 0 && count % 12 != 0 && count % 13 != 0 && count % 14 != 0 && count % 15 != 0 && count % 16 != 0 && count % 17 != 0 && count % 18 != 0 && count % 19 != 0 && count % 20 != 0 ; count++) {
			System.out.println(count);
		}
	}
}

**Norm** · May 31st, 2010, 03:05 PM

it still dosent work

Can you describe what happens?

As a suggestion for debugging your algorithm, use a smaller number such as 5 to validate the code works, then change to the larger number. Less debug output and faster executing times.

**helloworld922** · May 31st, 2010, 03:07 PM

One last small modification. I'll let you see if you can figure out how to fix it, but here's a hint:

What happens when count is divisible by 2, but not 3? The logic would become true and true and false... = false (I'm ignoring the other comparisons for now, but in this case they don't matter).

**shemer77** · May 31st, 2010, 07:25 PM

I think I know what your getting at, i have an idea and ill see what I can do thanks!

**javapenguin** · June 3rd, 2010, 09:37 PM

Originally Posted by shemer77

Here is what I am trying to do
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Here are my 3 different sets of code, the first 2 I know are definatly wrong, and I am just wondering how i would change them to be correct, but the third one I dont understand why it is wrong

public class Main {
    private static String result;
        public static void main( String argv[] )   {
                int count = 7;
                if (count % 1 == 0 && count % 2 == 0 && count % 3 == 0 && count % 4 == 0 && count % 5 == 0 && count % 6 == 0 && count % 7 == 0 && count % 8 == 0 && count % 9 == 0 && count % 10 == 0 && count % 11 == 0 && count % 12 == 0 && count % 13 == 0 && count % 14 == 0 && count % 15 == 0 && count % 16 == 0 && count % 17 == 0 && count % 18 == 0 && count % 19 == 0 && count % 20 == 0){
                   System.out.println("result" + result);
                } else {
                    System.out.println("wrong");
                    int++;
                }
        }
}

public class Main {
    private static String result;
        public static void main( String argv[] )   {
                int count = 7;
                inner :
                count++;
                if (count % 1 == 0 && count % 2 == 0 && count % 3 == 0 && count % 4 == 0 && count % 5 == 0 && count % 6 == 0 && count % 7 == 0 && count % 8 == 0 && count % 9 == 0 && count % 10 == 0 && count % 11 == 0 && count % 12 == 0 && count % 13 == 0 && count % 14 == 0 && count % 15 == 0 && count % 16 == 0 && count % 17 == 0 && count % 18 == 0 && count % 19 == 0 && count % 20 == 0){
                   System.out.println("result" + result);
                } else {
                   count++;
                   continue inner;
                }
        }
}

public class Main {
 
	public static void main(String[] args) {
		System.out.println("Calcluate this mofo");
		for (int count = 1; count % 1 == 0 && count % 2 == 0 && count % 3 == 0 && count % 4 == 0 && count % 5 == 0 && count % 6 == 0 && count % 7 == 0 && count % 8 == 0 && count % 9 == 0 && count % 10 == 0 && count % 11 == 0 && count % 12 == 0 && count % 13 == 0 && count % 14 == 0 && count % 15 == 0 && count % 16 == 0 && count % 17 == 0 && count % 18 == 0 && count % 19 == 0 && count % 20 == 0; count++) {
			System.out.println(count);
		}
	}
}

This is the maximum possible answer for an int: 4,294,967,295 (2^32 -1)
This is what your answer should be: 2,432,902,008,176,640,000 (20!).
A long can have a maximum of : 18,446,744,073,709,551,615 (2^64 -1)

Perhaps you should use a long.

**Norm** · June 4th, 2010, 09:23 AM

This is the maximum possible answer for an int: 4,294,967,295 (2^32 -1)

Problem with this is that ints in java are signed. max= 2147483647 (2^31 -1)

**helloworld922** · June 4th, 2010, 07:01 PM

Originally Posted by javapenguin

This is the maximum possible answer for an int: 4,294,967,295 (2^32 -1)
This is what your answer should be: 2,432,902,008,176,640,000 (20!).
A long can have a maximum of : 18,446,744,073,709,551,615 (2^64 -1)

Perhaps you should use a long.

Actually, the answer to this problem is 232792560, which easily fits into an int (max size=2147483647).

See this post to see why

Thread: Trying 3 different ways to do the same thing, each one is wrong

LinkBack

Thread Tools

Display

Trying 3 different ways to do the same thing, each one is wrong

Related threads:

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

The Following User Says Thank You to helloworld922 For This Useful Post:

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Re: Trying 3 different ways to do the same thing, each one is wrong

Similar Threads

500 Ways to Print 1 to 10

any ways to run a class from another class?

Something is wrong? Please help.

What's wrong?!

don't know what's wrong