aspose file tools*
The moose likes Beginning Java and the fly likes ArrayList index out of bounds? Prime numbers? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "ArrayList index out of bounds? Prime numbers?" Watch "ArrayList index out of bounds? Prime numbers?" New topic
Author

ArrayList index out of bounds? Prime numbers?

Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

I have (I think) created an app that counts the number of prime numbers in a range. My app is based on the Sieve of Eratosthenes

I'm getting a runtime error.... maybe someone can take a look?

here's the method....



When you do things right, people won't be sure you've done anything at all.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007
    
    9
What does your error message say?

Also, what is "indexMark ^ 2" intended to do?
Suchitra K Bhat
Greenhorn

Joined: Nov 04, 2009
Posts: 8
Array or List index starts from 0. Hence the last object is always at the index size-1.
When you try primes.get(primes.size()) - index primes.size() is out of reach in other words out of bounds for primes arraylist.
Hope this helps.
Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

Mike Simmons wrote:What does your error message say?

ArrayList Index out of bounds.... here's the cut and paste:



Also, what is "indexMark ^ 2" intended to do?

I need to square the indexMark..... or indexMark to the second power. The loop needs to end when (the value in the indexMark) squared is greater than the value in the last index of the ArrayList.
Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

I think I figured part of the problem out....

I changed it to


But it still gives a runtime error on that line
Suchitra K Bhat
Greenhorn

Joined: Nov 04, 2009
Posts: 8
Hey

try this.

Change this line while ((primes.get(indexMark) ^ 2) <= primes.get(primes.size())) to while ((primes.get(indexMark) ^ 2) <= primes.get(primes.size()-1))
Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

I did try that, then I realized that I increment the indexMark before the loop ends. I changed it to:



But now it just appears to freeze instead of continuing. Not sure why.

Here's the whole method as it stands now:

Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007
    
    9
Janeice DelVecchio wrote:
Mike Simmons wrote:Also, what is "indexMark ^ 2" intended to do?

I need to square the indexMark..... or indexMark to the second power. The loop needs to end when (the value in the indexMark) squared is greater than the value in the last index of the ArrayList.

I don't think that symbol means what you think it does.
Suchitra K Bhat
Greenhorn

Joined: Nov 04, 2009
Posts: 8
Is this part correct?

for (int x = indexMark; x < primes.size(); x++) {
if (primes.get(x) % primes.get(indexMark) == 0) {
primes.remove(x);
}
indexMark++;

}

If I trace this, first iteration X is Zero and indexMark is Zero
primes.get(0) % primes.get(0) == 0 -- this is true and removes the object at index Zero

Next iteration that when x=1, at this point indexMark is also 1 , this way all objects inside primes arrayList gets removed by the time "(primes.get(indexMark - 2) ^ 2) <= primes.get(primes.size() -1)" is reached.
Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

THANKS! it works now!

Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

ummmmm

I got too happy too soon.

My logic must not be correct. It's outputting all odd numbers. So the loop never gets to finding the multiples of 5 and taking them out....

What am I doing wrong?
Suchitra K Bhat
Greenhorn

Joined: Nov 04, 2009
Posts: 8
How about this? Please remove the hardcoding int choice = 12; , i did it for just testing.

This outputs "2 3 5 7 11 countPrimes returned == 5"

import java.util.*;
public class Test {

public static void main(String args[]) {
Test testObj = new Test();
System.out.print("countPrimes returned == "+testObj.countPrimes());
}

public int countPrimes() {
int choice = 12; //You can remove this hard coding
List<Integer> primes = new ArrayList<Integer>(choice);

for (int x = 2; x <= choice; x++) {
primes.add(x);
}
int indexMark = 2;
do {
for (int x = 0; x < primes.size(); x++) {
if ( (primes.get(x)>indexMark) && (primes.get(x) % indexMark == 0)) {
primes.remove(x);
}
}
indexMark++;
} while ((indexMark ^ 2) <= primes.get(primes.size() -1));

for (int x = 0; x < primes.size(); x++) {
System.out.print(primes.get(x) + " ");
}
return primes.size();
}
}
Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

It's still not getting rid of the multiples of 3 or 5 or 7 or higher.

Something is wrong with my algorithm I think... and I'm not seeing it.

For example: Input of 30
It's supposed to go through the first time and take out the multiples of 2.
That leaves: 2, 3, 5, 7, 9, 11, 13, 15, 19, 21, 23, 25, 27, 29.
Index^2 = 4 which is less than 30 so keep going.

Then it goes to the next index, 3, and takes out all those multiples.
That leaves: 2, 3, 5, 7, 11, 13, 19, 23, 25, 29
Index^2 = 9.... again less than 30 so keep going.

Then it goes to the next index, 5, and takes out all those multiples.
That leaves: 2, 3, 5, 7, 11, 13, 19, 23, 29
Index^2 = 25... keep going.

Then it goes to the next index, 7, and should remove nothing.
Index^2 = 49 which is greater than 30 so STOP

Here's what I have now:

Suchitra K Bhat
Greenhorn

Joined: Nov 04, 2009
Posts: 8
your countPrimes() is not correct.
Changes you need are

1) indexMark should be incremented out side for loop but inside the do-while loop
2) first for loop should start with 0 not with indexMark

countPrimes() given below works fine. I have tried the below countPrimes() with 30 which gives the out put of 2 3 5 7 11 13 17 19 23 29

public int countPrimes() {
List<Integer> primes = new ArrayList<Integer>(choice);

for (int x = 2; x <= choice; x++) {
primes.add(x);
}
int indexMark = 2;
do {
for (int x = 0; x < primes.size(); x++) { // --> Here x is Zero not indexMark
if ( (primes.get(x)>indexMark) && (primes.get(x) % indexMark == 0)) {
primes.remove(x);
}
} // --> for loop is closed here note that indexMark is incremented after closing the for loop
indexMark++;
} while ((indexMark ^ 2) <= primes.get(primes.size() -1));

for (int x = 0; x < primes.size(); x++) {
System.out.print(primes.get(x) + " ");
}
return primes.size();
}
Suchitra K Bhat
Greenhorn

Joined: Nov 04, 2009
Posts: 8
and "^" this symbol in java is to indicate power of

For eg
2 ^ 2 will be 2 power 2 i.e 2 *2
2 ^ 3 is 2 power 3 i.e 2 * 2 * 2

Similarly

indexMark ^ 2 == indexMark * indexMark . You can use ^ and do not need to use indexMarkSqd.
Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

Thanks SO much! It works great now!
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007
    
    9
Apparently I was too indirect in my previous posts. Let me fix that:

In Java, the symbol does NOT indicate "power" or "to the power of". EVER. You guys are thinking of other languages.

It's easy to test this:

So, what does the ^ really do in Java? Well, it's not really relevant here, but if you're interested, I'd start with the Java Tutorial's section on Operators.

If you want to square a number in Java, just multiply it by itself. So for example

could be replaced with


I make no comment on whether this algorithm looks correct or not; I haven't analyzed it at all. I'm just commenting on the basics of what ^ means in Java.
Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

Thanks for setting this straight.... back to the drawing board.

Rome wasn't built in a day, right?

EDIT: I changed it, and it works exactly the same.....just sayin.....
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: ArrayList index out of bounds? Prime numbers?