# Find the 10001st Prime Number

Page 1 of 1

## 10 Replies - 6989 Views - Last Post: 13 September 2010 - 01:56 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=190218&amp;s=dc4e9aa976e80079052c2b334fb54059&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Brewer

• Awesome

Reputation: 179
• 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

• XNArchitect

Reputation: 1357
• 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?

### #3 Brewer

• Awesome

Reputation: 179
• 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.

### #4 Kilorn

• XNArchitect

Reputation: 1357
• 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

### #5 Brewer

• Awesome

Reputation: 179
• 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.

### #6 Kilorn

• XNArchitect

Reputation: 1357
• 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.

### #7 Brewer

• Awesome

Reputation: 179
• 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

Reputation: 32
• 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

### #9 KYA

• g++ jameson.cpp -o beverage

Reputation: 3145
• Posts: 19,185
• 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.

### #10 Brewer

• Awesome

Reputation: 179
• 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!

### #11 Dogstopper

Reputation: 2920
• Posts: 11,195
• Joined: 15-July 08

## Re: Find the 10001st Prime Number

Posted 13 September 2010 - 01:56 PM

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.