# Question About Finding Prime Numbers (Java)

Page 1 of 1

## 11 Replies - 4217 Views - Last Post: 02 October 2011 - 10:21 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=249568&amp;s=5021c94fa5d3ba7d5a0cd0f674b2dc22&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 jacobsnakob94

Reputation: 1
• Posts: 13
• Joined: 02-October 11

# Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 06:57 PM

I'm fairly new to programming, so please don't be too mean if my code is poorly structured or nonsensical!

I'm attempting problem 7 on Project Euler. It is asking for the 10,001th prime number. Now, in my head I have a good idea on how to tackle this one systematically, but I'm having a hard time translating this into code. My method for finding this prime number is this (please tell me if there are any flaws in my logic!):

Any number that is not prime can be broken up into smaller prime numbers. Thus, if some number n cannot be divided evenly into any of the prime numbers smaller than it, then n must be a prime number. With that being said, one could identify the 10,001th prime number by starting at 2, adding 1 (3), and checking to see if this number can be divided evenly by 2. Since 3 cannot be divided evenly by 2, it is also prime and can be added to the "prime list". Then the next number, 4, could be checked by dividing it by 2 and 3. Since it can be divided by at least one of these numbers (2), then it is not prime. Then 5 would be checked, and since it cannot be evenly divided by 2 or 3, it is prime and would be added to the list. This process would continue until 10001 prime numbers are present in the list, and the final one would be the answer.

I know that was probably an unnecessary explanation, but I wanted to give a clear explanation of my intention behind writing my code. So..here it is:

```package find.a.prime.number;
import java.util.Scanner;

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int[] numberOfprimes = new int[10001];
numberOfprimes[0] = 2;
int test = 3;
int numberIndices = 0;
int b = 0;
int a = 0;

while(numberIndices <= 10001){
while(b <= numberIndices){
if(test%numberOfprimes[b]!= 0){
if(b == numberIndices){
numberOfprimes[b] = a;
numberIndices = numberIndices + 1;
}
b = b + 1;

}
else{
test = test + 1;
break;
}
}
b=1;

}

System.out.println("The 10,001st prime number is " + test);

}
}

```

Alright, so here are my two questions..
1) Am I even approaching this correctly? If not, feel free to nudge me in the right direction. And by nudge, I do not mean "give me the answer". I'd like to figure this out on my own.
2) When I compile this program, it says that I can't "divide by zero" on the line "if(test%numberOfprimes[b] != 0){". Why is it doing that? When does numberOfprimes[b] ever equal zero?

Thanks in advance for taking your time reading this! And again, try not to judge me too harshly! I just started learning this a couple days ago, so I'm still very much a novice..
-Jacob

This post has been edited by jacobsnakob94: 02 October 2011 - 07:00 PM

Is This A Good Question/Topic? 0

## Replies To: Question About Finding Prime Numbers (Java)

### #2 fromTheSprawl

• Bloodborne

Reputation: 522
• Posts: 2,102
• Joined: 28-December 10

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:07 PM

The variable b in your main method declaration isn't accessible inside that while statement. So it assumes that b is local inside that while loop and doesn't have a value.

By the way, why not use for loops?

### #3 jacobsnakob94

Reputation: 1
• Posts: 13
• Joined: 02-October 11

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:27 PM

fromTheSprawl, on 02 October 2011 - 07:07 PM, said:

The variable b in your main method declaration isn't accessible inside that while statement. So it assumes that b is local inside that while loop and doesn't have a value.

By the way, why not use for loops?

Well, to answer your question, I'm kind of learning this on a "learn-new-things-as-I-need-them" basis. I just learned the basics and started doing problems on Project Euler from there, researching new things as I go. I didn't even know how to write arrays and such before this particular problem. So, I haven't looked into for-loops, but if they would provide a better alternative, then I'm more than willing to learn now!

### #4 pbl

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

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

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:32 PM

You make it complicated for nothing...
and actually discussed one of the most discussed algorithm

here is an easy one (not tested)
```public class Prime {

public static void main(String[] arg) {
int[] firstPrime = new int[1000];
firstPrime[0] = 2;
firstPrime[1] = 3;
int primeFound = 2;

for(int i = 5; i < 9999999; i += 2) {
int j = 1;
for(; j < primeFound; ++j) {
if(i % firstPrime[j] == 0) {
break;
}
}
if(j == primeFound) {
firstPrime[primeFound++] = i;
if(primeFound == firstPrime.length) {
System.out.println("The " + firstPrime.length + "th prime is: " + i);
break;
}
}

}

}
}

```

but the ultimate one is there

http://www.dreaminco...-prime-numbers/

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12314
• Posts: 45,411
• Joined: 27-December 08

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:35 PM

I used the Sieve of Eratosthenes to do this, and just generated additional numbers if I found myself lacking. So if I found all the primes between 2-10000 and found myself only having 1000 primes, I'd add numbers from 10001-12000 (as an example) to the List and sieve those. Repeating until I had 10001 primes. You may find an ArrayList helpful here.

Some tutorials you may find helpful from Locke:
Looping
ArrayLists vs. Static Arrays

### #6 burakaltr

• D.I.C Regular

Reputation: 91
• Posts: 280
• Joined: 07-November 10

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:39 PM

Here's an Alternative one

```import java.util.Scanner;

public class Primer{

public static void main(String args[]){
boolean bool;
int i,j;
while(true){
int min=0,max=100000000;	{
int n=0,k=0;
//	while(true){
//	System.out.println(" Enter min , max")	;
Scanner in=new Scanner(System.in);
System.out.println(" Enter N for the nth PRIME");
k=in.nextInt();
//		min=in.nextInt();
//		max=in.nextInt();
if(min<0)min=1;
if(min==0)min=min+1;

for(i=min;i<max+1;i++)

{
bool=false;

if(i==1)i++;
for(j=2;j<i;j++)
{

if(i%j==0){bool=true;
if(i==2)break;

break;	}
if(bool==true)
{
i++;

}
}

if(bool==false)

{
n++;
System.out.println(i+" is a Prime ");

if(n==k)
{
System.out.println(" The Prime "+n+ " th Prime is :"+i);
break;
}
}
}

}
}}

}

```

### #7 jacobsnakob94

Reputation: 1
• Posts: 13
• Joined: 02-October 11

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:44 PM

macosxnerd101, on 02 October 2011 - 07:35 PM, said:

I used the Sieve of Eratosthenes to do this, and just generated additional numbers if I found myself lacking. So if I found all the primes between 2-10000 and found myself only having 1000 primes, I'd add numbers from 10001-12000 (as an example) to the List and sieve those. Repeating until I had 10001 primes. You may find an ArrayList helpful here.

Some tutorials you may find helpful from Locke:
Looping
ArrayLists vs. Static Arrays

Ooh! That is interesting! I've never heard of the Sieve of Eratosthenes! I think I will try this method . Thanks for the help!

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12314
• Posts: 45,411
• Joined: 27-December 08

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:44 PM

A note that the Sieve of Eratosthenes generates primes from 2-n. But it's a good place to start. Glad I could help!

### #9 pbl

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

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

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:46 PM

```import java.util.Scanner;

public class Primer{

public static void main(String args[]){
boolean bool;
int i,j;
while(true){
int min=0,max=100000000;	{
int n=0,k=0;
//	while(true){
//	System.out.println(" Enter min , max")	;
Scanner in=new Scanner(System.in);
System.out.println(" Enter N for the nth PRIME");
k=in.nextInt();
//		min=in.nextInt();
//		max=in.nextInt();
if(min<0)min=1;
if(min==0)min=min+1;

for(i=min;i<max+1;i++)
{
bool=false;

if(i==1)i++;
for(j=2;j<i;j++)
{
if(i%j==0){bool=true;
if(i==2)break;

break;	}
if(bool==true)
{
i++;

}
}

if(bool==false)
{
n++;
System.out.println(i+" is a Prime ");

if(n==k)
{
System.out.println(" The Prime "+n+ " th Prime is :"+i);
break;
}
}
}

}
}}

}

```

And this code is actually much more complicated than the original OP post
and
for(i=min;i<max+1;i++)
no need to test all even number, i +=2 would be a lot more efficient

This post has been edited by pbl: 02 October 2011 - 07:51 PM

### #10 burakaltr

• D.I.C Regular

Reputation: 91
• Posts: 280
• Joined: 07-November 10

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 07:51 PM

pbl, on 02 October 2011 - 07:46 PM, said:

```import java.util.Scanner;

public class Primer{

public static void main(String args[]){
boolean bool;
int i,j;
while(true){
int min=0,max=100000000;	{
int n=0,k=0;
//	while(true){
//	System.out.println(" Enter min , max")	;
Scanner in=new Scanner(System.in);
System.out.println(" Enter N for the nth PRIME");
k=in.nextInt();
//		min=in.nextInt();
//		max=in.nextInt();
if(min<0)min=1;
if(min==0)min=min+1;

for(i=min;i<max+1;i++)
{
bool=false;

if(i==1)i++;
for(j=2;j<i;j++)
{
if(i%j==0){bool=true;
if(i==2)break;

break;	}
if(bool==true)
{
i++;

}
}

if(bool==false)
{
n++;
System.out.println(i+" is a Prime ");

if(n==k)
{
System.out.println(" The Prime "+n+ " th Prime is :"+i);
break;
}
}
}

}
}}

}

```

And much more complicated than the original OP post
and
for(i=min;i<max+1;i++)
no need to test all even number, i +=2 would be a lot more efficient

Yes, thank you.

I was experimenting.

Thanks again for the suggestion.

### #11 jacobsnakob94

Reputation: 1
• Posts: 13
• Joined: 02-October 11

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 10:18 PM

I got it all figured out . Thank you all for the help!

### #12 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12314
• Posts: 45,411
• Joined: 27-December 08

## Re: Question About Finding Prime Numbers (Java)

Posted 02 October 2011 - 10:21 PM