[Brewer]

Yep, another Euler problem from yours truly. I don't know why this isn't work (just like with everything else I post here). The idea seems right to me, but I think I am making a noobish mistake something.

/*
//    Project Euler
//    Problem #: 7
//    By: TheEngineer
//    Date: 09/12/10
*/

public class Euler7 {

    public static void main(String args[]) {
    
        int[] primes = new int[10002];
        int tmp = 0;

        for ( int i = 2; i < 10000000; i++ ) { // Search for primes up to the number 1,000,000
            int j = 0; // primes[j] goes from places 0 to 10,001.

            while ( j < 10002 ) {

                if ( isPrime(i) && i > tmp ) {
                    primes[j] = i;
                    tmp = i;
                    j++; 
                }
                break;
            }
        }

        System.out.println(primes[10001]); // Print the 10,001st prime number
    
    }
    
    public static boolean isPrime( int x ) { // Checks to see if a number is prime

        for ( int i = 2; i <= x / 2; i++ ) { // i starts at 2, while i < half of x (int i from main), incriment i by one each time we loop
            if ( x % i == 0 ) { // if x is divisible by any number that is <= half of it, then x is NOT prime
                return false;
            }
        }
        return true; // If x isn't divisible by any number other than itself and one, then x IS prime
    }
    
}

I tried commenting this time, hope that helps. The reason I decided to use a while loop, incrementing j by 1 each time, was because I thought this would save a lot of time. Rather than looping through every number between 2 and 1,000,000 over 10,000 times. I could be wrong but this makes sense to me.

Tell me why I am wrong please.

[Kilorn]

What, if anything, does the code actually print?

[Brewer]

It doesn't print anything. I can add in some prints for debugging and they will show up. As it stands now though, it doesn't print anything at all.

[Kilorn]

Are you sure the 10001st prime number isn't greater than 1,000,000? If there are less than 10001 prime numbers between 0 and 1,000,000, then there wouldn't even be a value to print at that index.

EDIT: Nevermind, I just googled it and I see that the 10001st prime number is 104,743.

This post has been edited by Kilorn: 13 September 2010 - 10:20 AM

[Brewer]

Ok, well now I need to create a program that returns 104,743.

[Kilorn]

This is definitely not an issue, but I just noticed that you're actually looking at all numbers up to 10,000,000 instead of 1,000,000.

[Brewer]

That would multiply the time it takes for the program to complete by 10, so I think it could be a bit of an issue.

EDIT: I changed the number to 125,000, just above the 10,001st prime number. However, the program now returns 0! It should also be known that the program returns 0 for the value of primes[0] as well.

This post has been edited by .TheEngineer: 13 September 2010 - 11:17 AM

[javadork]

Your code is resetting j each time through the for loop in main so your result is always appearing in primes[0]. Move

int j = 0; // primes[j] goes from places 0 to 10,001.

right before the for loop commences, and maybe that'll help. (I haven't tested that fix.)

[Edited to edit my bad editing.]

This post has been edited by javadork: 13 September 2010 - 11:39 AM

[KYA]

One way to approach this:

while(true)
increment current number
check if prime
increment counter if found
if counter equals 10001 return most recently found prime


No need to store all of the primes.

[Brewer]

It took me a minute to get my algorithm correct, but your way worked KYA. Thanks again!

[Dogstopper]

KYA, on 13 September 2010 - 02:10 PM, said:

One way to approach this:

while(true)
increment current number
check if prime
increment counter if found
if counter equals 10001 return most recently found prime


No need to store all of the primes.

You can optimize this algorithm by only checking odd numbers and numbers that aren't multiples of a number that you've already tried.