My program is a implementation of the Sieve of Eratosthenes algorithm, which finds primes number. It stores two integers up to the maximum, and all odd numbers from 3 upward. It also checks if, for whatever any reason the first number ever reached the square root of the maximum number, all the remaining values from the number list are moved into the primes list. My problem is I keep reaching an error that says

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size: 1
at java.util.LinkedList.entry(LinkedList.java:365)
at java.util.LinkedList.get(LinkedList.java:315)
at Sieve.sieve(Sieve.java:52)
at Sieve.main(Sieve.java:16)

everytime I enter 25, I get the above runtime error. Here's my code:

// Uses a linked list to implement the Sieve of
	// Eratosthenes algorithm for finding prime numbers.
	 
	import java.util.*;
	 
	public class Sieve {
	    public static void main(String[] args) {
	        System.out.println("This program will tell you all prime");
	        System.out.println("numbers up to a given maximum.");
	        System.out.println();
	         
	        Scanner console = new Scanner(System.in);
	        System.out.print("Maximum number? ");
	        int max = console.nextInt();
	         
	        LinkedList<Integer> primes = sieve(max);
	        System.out.println("Prime numbers up to " + max + ":");
	        System.out.println(primes);
	    }
	 
	    // Returns a list of all prime numbers up to the given maximum
	    // using the Sieve of Eratosthenes algorithm.
	    public static LinkedList<Integer> sieve(int max) {
	        LinkedList<Integer> primes = new LinkedList<Integer>();
	 
	        // add all numbers from 3 to max to a list
	        LinkedList<Integer> numbers = new LinkedList<Integer>();
	        if (max >= 2)
	          {
	              numbers.add(2);
	              for (int i = 3; i <= max; i += 2)
	              {
	                  numbers.add(i);
	              }
	          }
	        while (!numbers.isEmpty()) {
	            // remove a prime number from the front of the list
	            int front = numbers.remove(0);
	            primes.add(front);
	 
	            // remove all multiples of this prime number
	            Iterator<Integer> itr = numbers.iterator();
	            while (itr.hasNext()) {
	                int current = itr.next();
	                if (current % front == 0) {
	                    itr.remove();
	                }
	                      
	                // If the first number reaches the square root of max, all
	                // other numbers are moved into the primes list  
	                     if (front >= Math.sqrt(max))
	                    {
	                       for(int i = 2; i * i <= max; i++)
	                       {
	                           primes.add(numbers.get(i));
	                       }
	                    }
	            }
	        }
	        return primes;
	    }
	}

Recommended Answers

All 6 Replies

Hey!

This is my new messaje. I debugged your code and it seems on row 55 you are trying to remove a list element of nonexisting index (too big). You might try replacing row 53 with this one: 'for(int i = 2; i * i <= max && i < numbers.size(); i++)'. This ensures you never remove an element of too big index.

Thanks for the response, but when I ran the program and punched in 25, it output:

Maximum number? 25
Prime numbers up to 25:
[2, 3, 5, 13, 17, 19, 23, 13, 17, 19, 23, 13, 17, 19, 23, 13, 17, 19, 23, 13, 17, 19, 23, 13, 17, 19, 23, 13, 17, 19, 23, 7, 17, 19, 23, 17, 19, 23, 17, 19, 23, 17, 19, 23, 17, 19, 23, 11, 19, 23, 19, 23, 19, 23, 19, 23, 13, 23, 23, 23, 17, 19, 23]

I just fixed the IndexOutOfBoundsException. If the output numbers are wrong you might have a problem in your algorithm. What is the expected sequence of numbers?

Maximum number? 25
Prime numbers up to 25:
[2, 3, 5, 13, 17, 19, 23]

Member Avatar for ztini

You missed some.

Here's a basic class I've used in the past:

public class Prime {
	public static boolean isPrime(int value) {
		for (double i = 2, max = value; i < max; i++) {
			if (value % i == 0) 
				return false;
			max = value / i;
		}
		return true;
	}
	public static void main(String[] args) {
		for (int i = 2; i < 25; i++) 
			if(isPrime(i)) 
				System.out.print(i + " ");
	}
}

Console: 2 3 5 7 11 13 17 19 23

ztini's code is nicer, clearer, shorter, elegant. However if you wish to use your algorithm add this: 'if (!primes.contains(front))' on row 33, this: 'if (!primes.contains(numbers.get(i)))' on row 54 and this: 'Collections.sort(primes);' on row 59... or just use below code! :)

public static LinkedList<Integer> sieve(int max) {
		LinkedList<Integer> primes = new LinkedList<Integer>();

		// add all numbers from 3 to max to a list
		LinkedList<Integer> numbers = new LinkedList<Integer>();
		if (max >= 2)
		{
			numbers.add(2);
			for (int i = 3; i <= max; i += 2)
			{
				numbers.add(i);
			}
		}
		while (!numbers.isEmpty()) {
			// remove a prime number from the front of the list
			int front = numbers.remove(0);
			if (!primes.contains(front))
				primes.add(front);

			// remove all multiples of this prime number
			Iterator<Integer> itr = numbers.iterator();
			while (itr.hasNext()) {
				int current = itr.next();
				if (current % front == 0) {
					itr.remove();
				}

				// If the first number reaches the square root of max, all
				// other numbers are moved into the primes list  
				if (front >= Math.sqrt(max))
				{
					for(int i = 2; i * i <= max && i < numbers.size(); i++) {
						if (!primes.contains(numbers.get(i)))
							primes.add(numbers.get(i));
					}
				}
			}
		}
		Collections.sort(primes);
		return primes;
	}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.