Using an int primitive type for i and j is causing the number to go through integer overflow integer overflow and go back to its minimum value -2,147,483,648 (or \$-2^{31}\$), once it exceeds the maximum value 2,147,483,647 (or \2ドル^{31}-1\$), then finally all the way back from there to \0ドル\$, resulting in a java.lang.ArithmeticException: divide by zero. To correct this, use a long type for the iterators instead:
Using an int primitive type for i and j is causing the number to go through integer overflow and go back to its minimum value -2,147,483,648 (or \$-2^{31}\$), once it exceeds the maximum value 2,147,483,647 (or \2ドル^{31}-1\$), then finally all the way back from there to \0ドル\$, resulting in a java.lang.ArithmeticException: divide by zero. To correct this, use a long type for the iterators instead:
Using an int primitive type for i and j is causing the number to go through integer overflow and go back to its minimum value -2,147,483,648 (or \$-2^{31}\$), once it exceeds the maximum value 2,147,483,647 (or \2ドル^{31}-1\$), then finally all the way back from there to \0ドル\$, resulting in a java.lang.ArithmeticException: divide by zero. To correct this, use a long type for the iterators instead:
The "right" algorithm is very simple, and involves no primality testing. I left an explanation of it in the code comments. This finds the right answer in less than 1 second. There would be other ways to improve it to be more Java/object-oriented, but for the sake of a math exercise like this it should do pretty nicely. Here is a live demo live demo as well.
class LargestPrimeFactor {
public static void main(String[] args) {
long N = 600851475143L;
// First, start from the maximum number and divide by 2
// until you can no longer divide evenly by 2, i.e., the number is odd
while (N % 2 == 0) {
// in the case of 600851475143 this will be skipped entirely since it is an odd number,
// but for the sake of generality we will keep it so it can be used on any number
N /= 2;
}
// the next prime number is 3, and all prime numbers from there are odd numbers,
// so we can safely just add 2 to the factor each time and only test for odd numbers
// note that this has a small inefficiency in that it will also test for a few non-prime odd numbers
// like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
for (long factor = 3; factor < N; factor += 2) {
// if N is evenly divisible by the factor, then we just divide it, and we keep going
// until N can no longer be divided by a number smaller than itself,
// in other words, until N is a prime number
while (N % factor == 0 && factor < N) {
N /= factor;
}
}
System.out.println("The answer is " + N);
}
}
The "right" algorithm is very simple, and involves no primality testing. I left an explanation of it in the code comments. This finds the right answer in less than 1 second. There would be other ways to improve it to be more Java/object-oriented, but for the sake of a math exercise like this it should do pretty nicely. Here is a live demo as well.
class LargestPrimeFactor {
public static void main(String[] args) {
long N = 600851475143L;
// First, start from the maximum number and divide by 2
// until you can no longer divide evenly by 2, i.e., the number is odd
while (N % 2 == 0) {
// in the case of 600851475143 this will be skipped entirely since it is an odd number,
// but for the sake of generality we will keep it so it can be used on any number
N /= 2;
}
// the next prime number is 3, and all prime numbers from there are odd numbers,
// so we can safely just add 2 to the factor each time and only test for odd numbers
// note that this has a small inefficiency in that it will also test for a few non-prime odd numbers
// like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
for (long factor = 3; factor < N; factor += 2) {
// if N is evenly divisible by the factor, then we just divide it, and we keep going
// until N can no longer be divided by a number smaller than itself,
// in other words, until N is a prime number
while (N % factor == 0) {
N /= factor;
}
}
System.out.println("The answer is " + N);
}
}
The "right" algorithm is very simple, and involves no primality testing. I left an explanation of it in the code comments. This finds the right answer in less than 1 second. There would be other ways to improve it to be more Java/object-oriented, but for the sake of a math exercise like this it should do pretty nicely. Here is a live demo as well.
class LargestPrimeFactor {
public static void main(String[] args) {
long N = 600851475143L;
// First, start from the maximum number and divide by 2
// until you can no longer divide evenly by 2, i.e., the number is odd
while (N % 2 == 0) {
// in the case of 600851475143 this will be skipped entirely since it is an odd number,
// but for the sake of generality we will keep it so it can be used on any number
N /= 2;
}
// the next prime number is 3, and all prime numbers from there are odd numbers,
// so we can safely just add 2 to the factor each time and only test for odd numbers
// note that this has a small inefficiency in that it will also test for a few non-prime odd numbers
// like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
for (long factor = 3; factor < N; factor += 2) {
// if N is evenly divisible by the factor, then we just divide it, and we keep going
// until N can no longer be divided by a number smaller than itself,
// in other words, until N is a prime number
while (N % factor == 0 && factor < N) {
N /= factor;
}
}
System.out.println("The answer is " + N);
}
}
A small note first, please do not double-space all lines in code, it just makes it harder to read, rather than easier.
It checks every number \$i\$ in the set \$[2,3,4, \ldots, n-1]\$ to see if it is a factor of \$n\$.
For each \$i\$, it then checks every number \$j\$ in the set \$[i, i+1, i+2,\ldots, n-2]\$ to see if it is prime.
It returns each number that matches both criteria, e.g., \71,ドル 839, 1471\$71, 839, 1471 and finally the answer, and then it just keeps on going until \$i = 600851475143 - 1\$, which takes a very long time.
class LargestPrimeFactor {
public static void main(String[] args) {
long N = 600851475143L;
// First, start from the maximum number and divide by 2
// until you can no longer divide evenly by 2, i.e., the number is odd
while (N % 2 == 0) {
// in the case of 600851475143 this will be skipped entirely since it is an odd number,
// but for the sake of generality we will keep it so it can be used on any number
N /= 2;
}
// the next prime number is 3, and all prime numbers from there are odd numbers,
// so we can safely just add 2 to the factor each time and only test for odd numbers
// note that this has a small efficiencyinefficiency in that it will also test for a few non-prime odd numbers
// like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
for (long factor = 3; factor < N; factor += 2) {
// if N is evenly divisible by the factor, then we just divide it, and we keep going
// until N can no longer be divided by a number smaller than itself,
// in other words, until N is a prime number
while (N % factor == 0) {
N /= factor;
}
}
System.out.println("The answer is " + N);
}
}
A small note first, please do not double-space all lines in code, it just makes it harder to read rather than easier.
It checks every number \$i\$ in the set \$[2,3,4, \ldots, n-1]\$ to see if it is a factor of \$n\$.
For each \$i\$, it then checks every number \$j\$ in the set \$[i, i+1, i+2,\ldots, n-2]\$ to see if it is prime.
It returns each number that matches both criteria, e.g., \71,ドル 839, 1471\$ and finally the answer, and then it just keeps on going until \$i = 600851475143 - 1\$, which takes a very long time.
class LargestPrimeFactor {
public static void main(String[] args) {
long N = 600851475143L;
// First, start from the maximum number and divide by 2
// until you can no longer divide evenly by 2, i.e., the number is odd
while (N % 2 == 0) {
// in the case of 600851475143 this will be skipped entirely since it is an odd number,
// but for the sake of generality we will keep it so it can be used on any number
N /= 2;
}
// the next prime number is 3, and all prime numbers from there are odd numbers,
// so we can safely just add 2 to the factor each time and only test for odd numbers
// note that this has a small efficiency in that it will also test for a few non-prime odd numbers
// like 9, 15, 21, etc. but it's much less work to try dividing by a candidate factor than to test for primality.
for (long factor = 3; factor < N; factor += 2) {
// if N is evenly divisible by the factor, then we just divide it, and we keep going
// until N can no longer be divided by a number smaller than itself,
// in other words, until N is a prime number
while (N % factor == 0) {
N /= factor;
}
}
System.out.println("The answer is " + N);
}
}
A small note first, please do not double-space all lines in code, it just makes it harder to read, rather than easier.
It checks every number \$i\$ in the set \$[2,3,4, \ldots, n-1]\$ to see if it is a factor of \$n\$.
For each \$i\$, it then checks every number \$j\$ in the set \$[i, i+1, i+2,\ldots, n-2]\$ to see if it is prime.
It returns each number that matches both criteria, e.g., 71, 839, 1471 and finally the answer, and then it just keeps on going until \$i = 600851475143 - 1\$, which takes a very long time.
class LargestPrimeFactor {
public static void main(String[] args) {
long N = 600851475143L;
// First, start from the maximum number and divide by 2
// until you can no longer divide evenly by 2, i.e., the number is odd
while (N % 2 == 0) {
// in the case of 600851475143 this will be skipped entirely since it is an odd number,
// but for the sake of generality we will keep it so it can be used on any number
N /= 2;
}
// the next prime number is 3, and all prime numbers from there are odd numbers,
// so we can safely just add 2 to the factor each time and only test for odd numbers
// note that this has a small inefficiency in that it will also test for a few non-prime odd numbers
// like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
for (long factor = 3; factor < N; factor += 2) {
// if N is evenly divisible by the factor, then we just divide it, and we keep going
// until N can no longer be divided by a number smaller than itself,
// in other words, until N is a prime number
while (N % factor == 0) {
N /= factor;
}
}
System.out.println("The answer is " + N);
}
}