Java Prime Number Array Problem

[BirthofaNova]

I am having a humongous problem with an assignment in my Java class right now. Basically, I need to use to nested for loops and an array to calculate prime numbers. Each time I calculate a prime, I have to put it in the correct memory location in the array. Then I test each new number with the primes in the array to determine if it is prime or not.

public class PrimeArray
{
public static void main(String[] args)
{
int primes[];
int limit;
int place;
String output = "";
primes = new int[2000];
int primecount = 1;

String inputLimit = JOptionPane.showInputDialog("Please enter the highest prime to be calculated");
limit = Integer.parseInt(inputLimit);
primes[0]= 2;

for(int counter = 3; counter <=limit; counter ++)
{

for(int index =0; primes[index] <=counter); index++ )
{ if(counter%primes[index]==1)

This is about all I have so far. I know that I need some sort of counter to increment in order to keep track of what memory location I am at so the primes are put in the correct place in the array, but I can't get it to work properly. Quite honestly, I don't really expect any help, but I thought it might be worth a try.

[StarCleaver]

If you can be a little more specific on the what the program is doing, I will gladly help you. Be a bit more specific on what you mean by putting the primes in "the right memory location" and what you mean by using the primes to determine if a number is prime or not. Do you have a basic algorithm that you are using (something that one might do by hand) or do you have to make your own?

[BirthofaNova]

Tell you what, I will type up what the assignment sheet says. Here goes.

The program should outpall all prime numbers through the upper bound. While the prime numbers are being calculated, they should be added into an integer array, so that prime number calculation is more efficient. Only prime numbers should be divided into the new potential prime number. For example, if 2 does not divide into a potential prime number, they why attempt to divide 4,6,8,10, and so on into that number?

You will need nest for-loops to solve this problem. The outer loop will iterate over all potential prime numbers, starting at 2, while the inner loop should iterate over the values in your prime number array until the value of your array element is >= half the potential prime number.

So basically, the user inputs a number and the program is supposed to calculate all the prime numbers between 3 and that number. I then have to output all of the prime numbers in the array.

[StarCleaver]

At 11/2/06 09:25 PM, ForeverDecember wrote: Tell you what, I will type up what the assignment sheet says. Here goes.

The program should outpall all prime numbers through the upper bound. While the prime numbers are being calculated, they should be added into an integer array, so that prime number calculation is more efficient. Only prime numbers should be divided into the new potential prime number. For example, if 2 does not divide into a potential prime number, they why attempt to divide 4,6,8,10, and so on into that number?

You will need nest for-loops to solve this problem. The outer loop will iterate over all potential prime numbers, starting at 2, while the inner loop should iterate over the values in your prime number array until the value of your array element is >= half the potential prime number.

So basically, the user inputs a number and the program is supposed to calculate all the prime numbers between 3 and that number. I then have to output all of the prime numbers in the array.

Okay, that makes a lot more sense now. So I've implemented your assignment and I've got it working. The way I did it (maybe not the most efficient) if to have two for loops, as your instructor suggested. The first one iterates from 2 to the limit number and the inner loop iterates from 0 to the size of the array (which I made an ArrayList, but it still works with arrays). I mod the current value of the outer loop iterator variable (i in my case) with the iterator variable of the inner loop (j in my case). If j mod i is zero, we know i is not prime so we can set a boolean equal to false and break from the inner loop. However, if the boolean is not set to false during the entire iteration of the inner loop, we know the number is prime so we can add it to the array or ArrayList. I do this with an if() statement outside the closing bracket for the inner loop. This can continue and should add all the primes (at least mine does). You can then output the values of the array or ArrayList by iterating through it, or you can even output the values as you are iterating and avoid storing the primes in an array in the first place.

I know that that's probably not as specific as you wanted it to be, but give it a go and if you have questions I'll be checking the forums for another couple hours.

[BirthofaNova]

I'll take another look at it tomorrow morning...I would do it now, but I am too tired. Thanks for the help.

[authorblues]

i was gonna have a go at helping him. my java skills are weak these days, but i built this same program in flash, and even plotted them on a polar axis. shows a bit of neat number theory, if anyone is ever interested in seeing it. just thought id make a note...

At 11/2/06 10:13 PM, StarCleaver wrote: ...or you can even output the values as you are iterating and avoid storing the primes in an array in the first place.

printing them as you go would probably be quicker, but you still have to store the primes. its the only way to check if larger numbers are prime quickly and efficiently.

[RageOfOrder]

At 11/2/06 10:13 PM, StarCleaver wrote: I know that that's probably not as specific as you wanted it to be, but give it a go and if you have questions I'll be checking the forums for another couple hours.

Only problem with your implementation is that it's not efficient, like the assignment wants. You're comparing every possibility, which isn't something you want to do when finding primes from 1 to say 2 billion.

I've whipped up a program that does it the proper way but since it's an assignment I suppoe I can't just give away the code.

So here we go.

I use a function called getPrimes, that returns an array. Defined as follows:
public static int[] getPrimes( int max_val ) { .... }

Now inside this loop you need an array to hold the primes, two integers to count with in your for loops, an integer to keep track of where you are inserting your next prime in the primeNumbers array, and finally, a boolean that is true by default.

When declaring your array, since you don't know how big it will be, you can't really set an exact size, so you set it to the max it can be. In this case, you can't have any more primes than the number of integers you are checking, so make the array the size of the limit number you are looking for.

Now your outer for loop simply starts at 2 and goes to your limit.
Call this variable i.

Inside, you have a second for loop, using the variable j. It starts at 0, and goes until the value in your primeNumbers array at index j is <= half of i.

On every iteration of that inner loop, you can use an if statement to check the remainder of dividing i by the prime number at index j in your array. Use % for this
If the remainder is zero, the numbers divide evenly and thus i cannot be prime. Change your boolean to reflect this.

Once your inner loop finishes, if isPrime is still true, then the number is true and you can add it to your primeNumbers array.

When you're done, return the array to main and print it.

You'll get some trailing zeroes because your array is too big, but that should be easy for you to deal with.

I did it in 47 lines, and I space my code out pretty heavily.

[RageOfOrder]

Here's a nice little screenshot :)

[RageOfOrder]

Sorry for the tripple post, but this idea kinda got catchy. Makes me wish my assignments were this easy again....

Anyway, I modified my file to run both efficiently and inefficiently and timed the results of each.

Kinda neat, on a count from 2 to 50,000
As you can see in the screenshot, the slow version, that compares every value every time takes almost 19 seconds to calculate the primes from 2 - 50,000
and the version that compares using only found primes takes just over 2 seconds. BIG difference.

[BirthofaNova]

God damnit. I cannot get this thing to work properly. Maybe someone can spot my mistake? This is the same problem I was having last night. public class PrimeArray
{
public static void main(String[] args)
{
int primes[];
int limit;
int place;
String output = "";

int primecount = 1;
boolean test=true;

String inputLimit = JOptionPane.showInputDialog("Please enter the highest prime to be calculated");
limit = Integer.parseInt(inputLimit);
primes = new int[limit];
primes[0]= 2;

for(int i = 3; i <=limit; i ++)
{

for(int j =0; primes[j] <=(i/2); j++ )
{ test = true;
if(i%primes[j]==0)
test = false;

}
if(test ==true)
{
primes[primecount]= i;
primecount++;
}
} //end outer for

for(int t =0; t<primes.length; t++)
{
System.out.print("\t" + primes[t]);

It doesn't put out the right numbers...I am not worrying about the trailing zeroes at the moment...I just need to get this to work...I have that class at 11.

[StarCleaver]

At 11/3/06 09:25 AM, ForeverDecember wrote: for(int i = 3; i <=limit; i ++)
{

for(int j =0; primes[j] <=(i/2); j++ )
{ test = true;
if(i%primes[j]==0)
test = false;

}
if(test ==true)
{
primes[primecount]= i;
primecount++;
}
} //end outer for

for(int t =0; t<primes.length; t++)
{
System.out.print("\t" + primes[t]);

It doesn't put out the right numbers...I am not worrying about the trailing zeroes at the moment...I just need to get this to work...I have that class at 11.

You can't set test equals to true where you are doing it. You need to do it outside of the inner for loop but inside the outer for loop. I hope you know why. If you change that, your code works fine. To eliminate the trailing zeros, just put an if around the System.out.print() that checks to see if the number is not zero and if it is, then print it.

[StarCleaver]

At 11/3/06 02:40 AM, RageOfOrder wrote: Only problem with your implementation is that it's not efficient, like the assignment wants. You're comparing every possibility, which isn't something you want to do when finding primes from 1 to say 2 billion.

That was a brief oversight on my part. I've fixed it and I think with the break in the inner for loop and the changed range on the inner for loop, it is about as efficient as it can be without changing the algorithm. I'm still using an ArrayList, however, because it is simpler albeit less efficient.

[StarCleaver]

At 11/3/06 03:02 AM, RageOfOrder wrote: and the version that compares using only found primes takes just over 2 seconds. BIG difference.

That seems high. Are you still using the JOptionPane to gather the input? Because if you are you are counting user response in your time, not just program runtime. I can run the bulk of the alogrithm (all the for loops and printing) with 2- 50000 in about 328 ms.

[RageOfOrder]

At 11/3/06 10:32 AM, StarCleaver wrote:

At 11/3/06 03:02 AM, RageOfOrder wrote: and the version that compares using only found primes takes just over 2 seconds. BIG difference.

That seems high. Are you still using the JOptionPane to gather the input? Because if you are you are counting user response in your time, not just program runtime. I can run the bulk of the alogrithm (all the for loops and printing) with 2- 50000 in about 328 ms.

I modified it to run from 2-50,000 with no output and no input from the user. It just runs.
Difference could lie in our processors or how much load my CPU was under when I ran it.

Oh wait, do you use break; in your loop? I was instructed explicitly when I learned java never to use break; except in a switch statement, so I don't use them. In this case it would be much more efficient to use one, though.

[RageOfOrder]

And well since it's almost 11:30 and he's already in class....
here's my code. Uncommented, but works :)
http://radiogrounds.../rageoforder/ng.java

[StarCleaver]

At 11/3/06 12:23 PM, RageOfOrder wrote: And well since it's almost 11:30 and he's already in class....
here's my code. Uncommented, but works :)
http://radiogrounds.../rageoforder/ng.java

When I run yours it runs faster than mine using the break in your code and my code. It's interesting to note how much faster the array is compared to ArrayList. I guess the difference would come from the ArrayList resizing the internal array.

That's also weird that you were taught to not use breaks outside of switch statements. That seems pretty foolish. I've never heard any reason why break shouldn't be used. Were you told why not to do that, or were you just supposed to accept it?

Here's my code:

import java.util.ArrayList;

import javax.swing.JOptionPane;

/**
* Prime Array constructs and prints out an array of prime numbers from 2 to the user inputted limit.
*
* @author sieversj. Created Nov 2, 2006.
*/
public class PrimeArray {

/**
* Does everything..
*
* @param args - unused
*/
public static void main(String[] args) {
int limit;
boolean prime = true;
int place = 2;
String inputLimit = JOptionPane.showInputDialog("Please enter the highest prime to be calculated");
limit = Integer.parseInt(inputLimit);
ArrayList<Integer> primes = new ArrayList<Integer>();
//Base case
primes.add(2);
System.out.println(2);
for (int i = place; i <= limit; i++) {
prime = true;
for (int j = 0; primes.get(j) <= i / 2; j++) {
if (i % primes.get(j) == 0) {
prime = false;
break;
}
}
if (prime) {
primes.add(i);
System.out.println(i);
}
}
// System.out.println((double) primes.size()/limit);
}
}