# ArrayList index out of bounds? Prime numbers?

posted 7 years ago

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....

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

Posts: 3090

14

Suchitra K Bhat

Greenhorn

Posts: 8

posted 7 years ago

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

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.

Mike Simmons wrote:What does your error messagesay?

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.

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

Suchitra K Bhat

Greenhorn

Posts: 8

posted 7 years ago

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:

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

Here's the whole method as it stands now:

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

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 7 years ago

I don't think that symbol means what you think it does.

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

Posts: 8

posted 7 years ago

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.

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.

Suchitra K Bhat

Greenhorn

Posts: 8

posted 7 years ago

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();

}

}

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();

}

}

posted 7 years ago

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:

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:

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

Suchitra K Bhat

Greenhorn

Posts: 8

posted 7 years ago

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();

}

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

Posts: 8

posted 7 years ago

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.

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.

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 7 years ago

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.

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.

It is sorta covered in the JavaRanch Style Guide. |