Trying 3 different ways to do the same thing, each one is wrong
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
Code :
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++;
}
}
}
Code :
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;
}
}
}
Code :
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);
}
}
}
Re: Trying 3 different ways to do the same thing, each one is wrong
Can you explain the algorithm(s) that you want to use?
Can you explain a bit more? Or show the output and explain why its wrong.
Re: Trying 3 different ways to do the same thing, each one is wrong
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)
Code :
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:
Code :
// 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.
Re: Trying 3 different ways to do the same thing, each one is wrong
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,
Re: Trying 3 different ways to do the same thing, each one is wrong
Quote:
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
Quote:
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.
Re: Trying 3 different ways to do the same thing, each one is wrong
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?
Re: Trying 3 different ways to do the same thing, each one is wrong
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.
Re: Trying 3 different ways to do the same thing, each one is wrong
Thanks for the reply. Its been a long time since college and set theory.
Re: Trying 3 different ways to do the same thing, each one is wrong
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
Code :
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);
}
}
}
Re: Trying 3 different ways to do the same thing, each one is wrong
Quote:
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.
Re: Trying 3 different ways to do the same thing, each one is wrong
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).
Re: Trying 3 different ways to do the same thing, each one is wrong
I think I know what your getting at, i have an idea and ill see what I can do thanks!
Re: Trying 3 different ways to do the same thing, each one is wrong
Quote:
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
Code :
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++;
}
}
}
Code :
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;
}
}
}
Code :
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.
Re: Trying 3 different ways to do the same thing, each one is wrong
Quote:
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)
Re: Trying 3 different ways to do the same thing, each one is wrong
Quote:
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 ;)
