10 Replies - 6313 Views - Last Post: 13 September 2010 - 01:56 PM Rate Topic: -----

#1 Brewer  Icon User is offline

  • Awesome
  • member icon

Reputation: 179
  • View blog
  • Posts: 1,044
  • Joined: 14-June 10

Find the 10001st Prime Number

Posted 13 September 2010 - 10:09 AM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Find the 10001st Prime Number

#2 Kilorn  Icon User is offline

  • XNArchitect
  • member icon



Reputation: 1356
  • View blog
  • Posts: 3,528
  • Joined: 03-May 10

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 10:13 AM

What, if anything, does the code actually print?
Was This Post Helpful? 0
  • +
  • -

#3 Brewer  Icon User is offline

  • Awesome
  • member icon

Reputation: 179
  • View blog
  • Posts: 1,044
  • Joined: 14-June 10

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 10:16 AM

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.
Was This Post Helpful? 0
  • +
  • -

#4 Kilorn  Icon User is offline

  • XNArchitect
  • member icon



Reputation: 1356
  • View blog
  • Posts: 3,528
  • Joined: 03-May 10

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 10:19 AM

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

Was This Post Helpful? 0
  • +
  • -

#5 Brewer  Icon User is offline

  • Awesome
  • member icon

Reputation: 179
  • View blog
  • Posts: 1,044
  • Joined: 14-June 10

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 10:21 AM

Ok, well now I need to create a program that returns 104,743.
Was This Post Helpful? 0
  • +
  • -

#6 Kilorn  Icon User is offline

  • XNArchitect
  • member icon



Reputation: 1356
  • View blog
  • Posts: 3,528
  • Joined: 03-May 10

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 10:25 AM

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.
Was This Post Helpful? 0
  • +
  • -

#7 Brewer  Icon User is offline

  • Awesome
  • member icon

Reputation: 179
  • View blog
  • Posts: 1,044
  • Joined: 14-June 10

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 11:15 AM

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

Was This Post Helpful? 0
  • +
  • -

#8 javadork  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 32
  • View blog
  • Posts: 135
  • Joined: 21-August 10

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 11:33 AM

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

Was This Post Helpful? 0
  • +
  • -

#9 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3124
  • View blog
  • Posts: 19,168
  • Joined: 14-September 07

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 12:10 PM

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.
Was This Post Helpful? 1
  • +
  • -

#10 Brewer  Icon User is offline

  • Awesome
  • member icon

Reputation: 179
  • View blog
  • Posts: 1,044
  • Joined: 14-June 10

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 01:10 PM

It took me a minute to get my algorithm correct, but your way worked KYA. Thanks again!
Was This Post Helpful? 0
  • +
  • -

#11 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Find the 10001st Prime Number

Posted 13 September 2010 - 01:56 PM

View PostKYA, 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1