# PE#7 finding the 10,001 prime number

Page 1 of 1

## 5 Replies - 661 Views - Last Post: 04 May 2013 - 02:45 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=320150&amp;s=10cf772e8c9370f486f0546d91c6556c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 CSatVTftw

• New D.I.C Head

Reputation: 4
• Posts: 42
• Joined: 16-April 13

# PE#7 finding the 10,001 prime number

Posted 02 May 2013 - 04:13 PM

So I have code that (in my mind) should work. I'm not sure what's missing. It's getting up to 104009, which is the 9935th prime. It's looping all the way to 10002, so I'm thinking I missed something in my isPrime? TIA.

```   public class PE7 {
public static void main(String[] args) {
int count = 0;
int num = 0;
while(count<=10001) {
num++;
if(isPrime(num)==true) {
count++;
}
}
System.out.println(num);
}
public static boolean isPrime(long num){
boolean isPrimeFlag = true;
int i = 2;
while(i<Math.sqrt(num)) {
if(num%i==0) {
isPrimeFlag = false;
break;
}
i++;
}
return isPrimeFlag;
}

}

```

``` ----jGRASP exec: java PE7
104009

----jGRASP: operation complete.

```

Is This A Good Question/Topic? 0

## Replies To: PE#7 finding the 10,001 prime number

### #2 pbl

• There is nothing you can't do with a JTable

Reputation: 8378
• Posts: 31,956
• Joined: 06-March 08

## Re: PE#7 finding the 10,001 prime number

Posted 02 May 2013 - 05:06 PM

And what is your question ?
Beside really but really inefficient code what is your problem
I have seen horrible code computing prime numbers but you are one of the worst one

Do you realize then while testing num = 12345

doing

while(i<Math.sqrt(num)) {

will compute Math.sqrt() which is probaly a costly operation 12345 times ?
You are owner of a company selling CPUs or what ?
Compute that sqrt() only once for God love ad store it in a temp variable !!!

and why repeating the previous calculations ?

also the i++ is ridiculous... why checking all even numbers ?
should start with i = 3 and then i += 2;

No problem />/>

This post has been edited by pbl: 02 May 2013 - 06:48 PM

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12276
• Posts: 45,364
• Joined: 27-December 08

## Re: PE#7 finding the 10,001 prime number

Posted 02 May 2013 - 06:43 PM

You can optimize some. Store the primes you already have. If the number isn't divisible by any of those, then it's a prime. So start at 2. Then the next number is 3, which is prime. Same for 5 and 7. Then when you get to 9, it's divisible by a prime in your list, so it's not prime.

### #4 CSatVTftw

• New D.I.C Head

Reputation: 4
• Posts: 42
• Joined: 16-April 13

## Re: PE#7 finding the 10,001 prime number

Posted 02 May 2013 - 07:00 PM

I know it's really inefficient. I haven't worked in Java in a long time so I'm just trying to get back into the basics again before I take my Java classes this summer semester.

I'm not understanding why the program is not counting up to 10002 even though it is looping that many times. When I add a System.out.println(count);, it spits out 10002, so why is it not giving me the 10001th prime?

Mac, can you explain that or give a short blip of an example?

### #5 Gungnir

• Your Imaginary Friend

Reputation: 152
• Posts: 527
• Joined: 21-May 11

## Re: PE#7 finding the 10,001 prime number

Posted 03 May 2013 - 04:43 AM

[spoiler alert!] You don't need to use long integers. I modified your code and got the answer 104,725 (which is correct).

You can half your execution time if you take into account that 2 is the only even prime number (so don't even bother checking them):
```		  if(isPrime(num))
count++;
//After 2, skip every even number
if(num < 3)
num++;
else
num += 2;

```

I'm fairly certain that your method is incorrect. You should try something more like:
```  public static boolean isPrime(int n) {
for(int i = 3; i * i <= n; i += 2) {
if(n % i == 0)
return false;
}
return true;
}

```

And whilst we're keeping count: On a 3GHz computer (variables, shmariables) with your current method:
```10001th Prime = 104005
Execution time: 133 milliseconds

```

But if you fix it up a little (don't call Math.sqrt(), don't check even numbers):
```10001th Prime = 104725
Execution time: 25 milliseconds

```

This post has been edited by Gungnir: 03 May 2013 - 04:56 AM

### #6 schutzzz

• D.I.C Regular

Reputation: 143
• Posts: 342
• Joined: 22-April 13

## Re: PE#7 finding the 10,001 prime number

Posted 04 May 2013 - 02:45 PM

is your 10,001st even correct? on the website it's 104,743 and that's also what I got running mine.

```public class Primes implements Runnable {

public boolean isPrime(int checkNum) {
double root = Math.sqrt(checkNum);
for(int i = 2; i <= root; i++) {
if(checkNum % i == 0)
return false;
}
return true;
}

public void run() {
int quantity = 10_001;
int numberOfPrimes = 0;
int entrant = 2;
while(numberOfPrimes < quantity) {
if(isPrime(entrant)) {
System.out.println(": " + entrant);
numberOfPrimes++;
}
entrant++;
}
}

public static void main(String[] arguments) {