7 Replies - 4123 Views - Last Post: 19 October 2009 - 05:18 PM Rate Topic: -----

#1 kru   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 48
  • Joined: 29-February 08

Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 03:14 PM

I needed to implement the Sieve of Eratosthenes using LinkedList but my code prints out all of the numbers instead of just the primes. Please tell me what I'm doing wrong.

import java.util.LinkedList;

public class EratosthenesV2 {

	public EratosthenesV2(){	

		//a) Have some way of representing all integers from 2 to n
		LinkedList sieve = new LinkedList();
		int size = 10;
		Integer n = new Integer(1);

		//b) initialize by setting all bits to 1 ('1' will eventually mean index is a prime)
		for(int i = 2; i < size; i++){
			sieve.add(new Integer(i));
		}

		int finalBit = (int)(Math.sqrt(size));
		System.out.println("finalBit = " + finalBit);

		//c) start by crossing off all multiples of 2
		for (int i = 2; i <= finalBit; i++){
		 //d) look in the list for next integer that wasn't crossed off
			if(sieve.contains(n)){
				for(int j = 2*1; j < size; j += 1){
					sieve.set(j, 0);
				} 
			}
		}

		//g) walk through your list and print out all integers not crossed off
		for(int i = 1; i < size; i++){
			if(sieve.contains(i)){
				System.out.println(i);
			}
		} 

	
	}	


	public static void main (String[] args){
		EratosthenesV2 app = new EratosthenesV2();
	}

}


Is This A Good Question/Topic? 0
  • +

Replies To: Sieve of Eratosthenes using Linked List

#2 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12360
  • View blog
  • Posts: 45,474
  • Joined: 27-December 08

Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 03:21 PM

I actually wrote a snippet on this if you want to check it out!

But anyways, here is the general process:
  -Fill the collection with numbers 2 to n.
  -For i = 0 to collection.length-1, incrementing i by 1 on each iteration
	  -For j = 0 to collection.length-1, increment j by one on each iteration
		   -If element i % element j == 0 and element i != element j
				   -Remove element j
		   End if
		End for
	End for



So, look into using the remove() method for LinkedList as well as the % operator.

Try implementing this and let us know if you need any more help!
Was This Post Helpful? 0
  • +
  • -

#3 kru   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 48
  • Joined: 29-February 08

Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 03:33 PM

I had to change the j to start at 1 because you can't divide by zero. I think it works but it keeps deleting some of the prime numbers in my console. The output I get is:

finalBit = 4
2
3
11
13
17
19


import java.util.LinkedList;

public class EratosthenesV2 {

	
	public EratosthenesV2(){	

		//a) Have some way of representing all integers from 2 to n
		LinkedList sieve = new LinkedList();
		int size = 20;
		
		//b) initialize by setting all bits to 1 ('1' will eventually mean index is a prime)
		for(int i = 2; i < size; i++){
			sieve.add(new Integer(i));
		}

		int finalBit = (int)(Math.sqrt(size));
		System.out.println("finalBit = " + finalBit);

		//c) start by crossing off all multiples of 2
		for (int i = 0; i <= sieve.size()-1; i++){
			for(int j=1; j <=sieve.size()-1; j++){
				if((i%j)==1 && i != j){
					sieve.remove(j);
				} 
			}
		}

		//g) walk through your list and print out all integers not crossed off
		for(int i = 1; i < size; i++){
			if(sieve.contains(i)){
				System.out.println(i);
			}
		} 


	}	


	public static void main (String[] args){
		EratosthenesV2 app = new EratosthenesV2();
	}

}



Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12360
  • View blog
  • Posts: 45,474
  • Joined: 27-December 08

Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 04:28 PM

In this segment:
for (int i = 0; i <= sieve.size()-1; i++){
			for(int j=1; j <=sieve.size()-1; j++){
				if((i%j)==1 && i != j){
					sieve.remove(j);
				} 



You compare i and j. In my algorithm, I meant the values at i and j, so sieve.get(i) and sieve.get(j). Also, you want to compare sieve.get(i)%sieve.get(j) == 0, not 1. If the remainder is 1, then sieve.get(i) isn't evenly divisible by sieve.get(j).

Also, I would initialize j to i+1 on each iteration, that way, it only checks the elements you haven't confirmed to be prime.
Was This Post Helpful? 1
  • +
  • -

#5 kru   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 48
  • Joined: 29-February 08

Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 04:50 PM

I get an error on sieve.get(i) % sieve.get(j) because they are objects.

for (int i = 0; i <= sieve.size()-1; i++){
			for(int j=i+1; j <=sieve.size()-1; j++){
				if(sieve.get(i) % sieve.get(j) == 0 && sieve.get(i) != sieve.get(j)){
					sieve.remove(j);
				} 
			}
		}

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12360
  • View blog
  • Posts: 45,474
  • Joined: 27-December 08

Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 05:04 PM

Declare your LinkedList as a LinkedList of Integers like so:
LinkedList<Integer> sieve = new LinkedList<Integer>();



Basically, this tells the LinkedList to only accept Integer values. You can substitute any reference datatype where I put Integer. If you declare the LinkedList without the angle brackets and datatype, it defaults to LinkedList<Object> implicitly. Also, this concept applies to many other collections you'll be working with like ArrayList, Map, Set and more.
Was This Post Helpful? 0
  • +
  • -

#7 pbl   User is offline

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

Reputation: 8379
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 05:13 PM

View Postkru, on 19 Oct, 2009 - 03:50 PM, said:

I get an error on sieve.get(i) % sieve.get(j) because they are objects.

for (int i = 0; i <= sieve.size()-1; i++){
			for(int j=i+1; j <=sieve.size()-1; j++){
				if(sieve.get(i) % sieve.get(j) == 0 && sieve.get(i) != sieve.get(j)){
					sieve.remove(j);
				} 
			}
		}

It is because it is an ArrayList of Integer objects

you can always

for (int i = 0; i <= sieve.size()-1; i++){
	 for(int j=i+1; j <=sieve.size()-1; j++){
			 int ii = sieve.get(i).intValue();
			 int jj = sieve.het(j).intValue();
			 if(ii % jj == 0 && ii != jj){
		sieve.remove(j);
			 } 
	  }
}

Was This Post Helpful? 0
  • +
  • -

#8 kru   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 48
  • Joined: 29-February 08

Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 05:18 PM

Thanks. It works now.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1