# Sieve of Eratosthenes using Linked List

Page 1 of 1

## 7 Replies - 4057 Views - Last Post: 19 October 2009 - 05:18 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=133046&amp;s=63962a8a4e30685f70c16889ccae40ab&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 kru

• New D.I.C Head

Reputation: 0
• 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
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++){
}

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

• Games, Graphs, and Auctions

Reputation: 12332
• Posts: 45,435
• 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!

### #3 kru

• New D.I.C Head

Reputation: 0
• 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
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++){
}

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

}

```

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12332
• Posts: 45,435
• 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.

### #5 kru

• New D.I.C Head

Reputation: 0
• 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);
}
}
}
```

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12332
• Posts: 45,435
• 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.

### #7 pbl

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

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

## Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 05:13 PM

kru, 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);
}
}
}
```

### #8 kru

• New D.I.C Head

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

## Re: Sieve of Eratosthenes using Linked List

Posted 19 October 2009 - 05:18 PM

Thanks. It works now.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }