[Brewer]

I am working on a problem that wants me to find the largest prime factor of a given number, and an example was given. To make sure my code was correct I tried to write a program that got the right answer for the example, unfortunately I ran into a problem.

This is the code I am using to determine whether or not a number is prime:

public static boolean isPrime(int x) {
	
		boolean isTrue = true;
	
		for ( int y = 2; y <= x/2; y++ ) {
	
			if ( x % y == 0 ) {
				isTrue = false;
			} else {
				isTrue = true;
			}

		}
		
		return isTrue;
	
	}

My program is returning non-prime numbers, so I screwed up in here somewhere. Can someone please show me where?

[Martyr2]

The problem is that when you do find the value of y that divides evenly into x, you set the value to false, but you don't stop. So it checks the next number which most likely does not fit, so it sets isTrue back to true. You don't need to continue once you found the answer. This will also improve your efficiency.

for ( int y = 2; y <= x/2; y++ ) {
	
    if ( (x % y) == 0 ) {
        return false;
    }

}

return true;

Hope this makes sense to you. Because you didn't stop, you were checking all numbers and if any of those numbers were not dividing evenly, it was resetting isTrue back to true after you had set it to false.

Enjoy!

This post has been edited by Martyr2: 27 August 2010 - 11:28 AM

[Brewer]

Thanks! That does make sense. This is what I originally tried actually, but instead of return true; being outside of the loop, I had it on the inside. Problem solved!

[macosxnerd101]

And to make it more efficient, you just have to iterate to sqrt(n), not n/2.

[Brewer]

So this is more efficient?

for ( int y = 2; y <= sqrt(x); y++ ) { 

[KYA]

For the purposes of this program it won't matter, but finding the square root is an approximation (requires many iterations internally) so it would be more efficient to do this:

for ( int y = 2; y*y <= x; y++ ) { 

[mostyfriedman]

KYA, on 27 August 2010 - 09:30 PM, said:

For the purposes of this program it won't matter, but finding the square root is an approximation (requires many iterations internally) so it would be more efficient to do this:

for ( int y = 2; y*y <= x; y++ ) { 

<=

[Brewer]

Well it works fine as it is. So I refuse to change it! Thanks for everyones help.

[KYA]

.i7, on 27 August 2010 - 12:58 PM, said:

Well it works fine as it is. So I refuse to change it!

Why ask if you're going to disregard any responses you get?

[Dogstopper]

.i7, on 27 August 2010 - 02:58 PM, said:

Well it works fine as it is. So I refuse to change it! Thanks for everyones help.

Bad way to approach the situation. Your algorithm is FARLY good. You could make it better by returning true if the number is 2 and then start the for loop at 3 and add 2 to y each time, not just 1.

OR, even more efficient is The Sieve of Eratosthenes

[macosxnerd101]

Not for simply checking a prime or finding the largest prime factor. The Sieve of Eratosthenes takes O(n^(3/2)) time, while simple iteration should take no more than O(n/2) time.

[Dogstopper]

macosxnerd101, on 27 August 2010 - 03:19 PM, said:

Not for simply checking a prime or finding the largest prime factor. The Sieve of Eratosthenes takes O(n^(3/2)) time, while simple iteration should take no more than O(n/2) time.

You're right, for checking a prime, it's over the top. However, in many of the Euler problems, I found it being MUCH faster than traditional methods. I just mistaook the usage of it