Skip to content

Instantly share code, notes, and snippets.

@muayyad-alsadi
Created July 5, 2014 13:06
Show Gist options
  • Save muayyad-alsadi/f518f3ae413fd801e496 to your computer and use it in GitHub Desktop.
Save muayyad-alsadi/f518f3ae413fd801e496 to your computer and use it in GitHub Desktop.
primes iterator and iterable
import java.util.*;
/*
you can use it like this
PrimesIterator primes=new PrimesIterator(10000);
while(primes.hasNext()){
System.out.println(primes.next());
}
*/
class PrimesIterator implements Iterator<Integer> {
protected boolean is_done=false, pending_value=false;
protected int i=2,j,n, value=0;
HashSet<Integer> compo;
PrimesIterator(int bound) {
n=bound;
compo=new HashSet(n);
}
public void clear() {
i=2;
is_done=false;
pending_value=false;
compo.clear();
}
protected void do_iteration() {
if (i>=n) {is_done=true; return;}
if (!compo.contains(i)) {
pending_value=true;
value=i;
for(j=i*2;j<n;j+=i) compo.add(j);
}
++i;
}
public boolean hasNext() {
while(!is_done && !pending_value) do_iteration();
return !is_done;
}
public Integer next() {
while(!is_done && !pending_value) do_iteration();
if (pending_value) {
pending_value=false;
return value;
} else throw new NoSuchElementException("Out of bound, you should call hasNext");
}
public void remove() {
if (value>0) pending_value=true;
else throw new IllegalStateException();
}
}
/*
you can use it like this
for(int p : new PrimesIterable(10000)){ System.out.println(p); }
*/
class PrimesIterable implements Iterable<Integer> {
protected int n;
PrimesIterable(int bound) { n=bound; }
public Iterator<Integer> iterator() {
return new PrimesIterator(n);
}
List<Integer> toArrayList() {
List<Integer> list = new ArrayList<Integer>(n);
Iterator<Integer> iter=new PrimesIterator(n);
while (iter.hasNext()) list.add(iter.next());
return list;
}
}
class PrimesTest {
public static void main(String[] args) {
int c;
long t0=System.currentTimeMillis();
for(c=0;c<500;++c) {
List<Integer> a=new PrimesIterable(10000).toArrayList();
//for(int p : new PrimesIterable(10000)){ }
}
System.out.println(System.currentTimeMillis()-t0);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment