Skip to content

Instantly share code, notes, and snippets.

@Xe
Created March 19, 2012 20:37
Show Gist options
  • Save Xe/2126902 to your computer and use it in GitHub Desktop.
Save Xe/2126902 to your computer and use it in GitHub Desktop.
Sieve
import java.util.LinkedList;
import java.util.Queue;
//Sam Dodrill
//assgn page: http://penguin.ewu.edu/cscd300/Winter_12/Assignments/prog4.html
public class Sieve {
private Queue<Integer> primes = new LinkedList<Integer>();
private int lastMax = 0;
private int lastCount = 0;
public void computeTo(int max) {
//Need to nuke these two lists
lastMax = max;
if(max < 3 && max > 0) {
primes = new LinkedList<Integer>();
primes.offer(1);
if(max == 2) {
primes.offer(2);
}
} else {
primes = sieve(max);
}
lastCount = primes.size();
}
public static LinkedList<Integer> sieve(int n){
Queue<Integer> primes = new LinkedList<Integer>();
Queue<Integer> nums = new LinkedList<Integer>();
for(int i = 2;i <= n;i++){
nums.add(i);
}
//I hate do...while loops, so I converted it to a standard while loop.
while(nums.size() > 0){
int nextPrime = nums.remove();
for(int i = nextPrime * nextPrime;i <= n;i += nextPrime){
((LinkedList<Integer>) nums).removeFirstOccurrence(i);
//I know we are supposed to be using Queues here, but
//the convenience of this function is worth it.
}
primes.offer(nextPrime);
}
return (LinkedList<Integer>) primes;
}
public void reportResults() {
int inLines = 0;
for (int i : primes) {
System.out.printf("%d\t", i);
inLines++;
if(inLines == 8) {
inLines = 0;
System.out.println();
}
}
System.out.println();
}
public int getCount() {
return lastCount;
}
public int getMax() {
// TODO Auto-generated method stub
return lastMax;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment