# import java util AbstractSet import java util Iterator import java uti

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113``` ```import java.util.AbstractSet; import java.util.Iterator; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class Factorial { public static void main(String[] args) { Scanner in = new Scanner(System.in); final int n = in.nextInt(); Set primes = new IntSparseSet(2, n+1) {{ for (int i = 2; i <= n; i++) add(i); for (int i = 2; i*i <= n; i++) { if (contains(i)) { for (int j = i*i; j <= n; j += i) remove(j); } } }}; for (int x : new TreeSet(primes)) { System.out.printf("%d ", x); } System.out.println(); } } class IntSparseSet extends AbstractSet { private int low, high, n; public int[] sparse, dense; public IntSparseSet(int l, int h) { low = l; high = h; sparse = new int[h-l]; dense = new int[h-l]; n = 0; for(int i=0;i=n || dense[sparse[x]] != x) { dense[n] = x; sparse[x] = n; n++; return true; } return false; } @Override public void clear(){ n = 0; } @Override public boolean contains(Object x){ x=(Integer)x-low; if(sparse[(Integer)x] < n && dense[sparse[(Integer)x]] == (Integer)x) return true; else return false; } @Override public boolean remove(Object x){ x=(Integer)x-low; if(sparse[(Integer)x] <= n-1 && dense[sparse[(Integer)x]] == (Integer)x){ dense[sparse[(Integer)x]] = dense[n-1]; sparse[dense[n-1]] = sparse[(Integer)x]; n--; return true; } return false; } @Override public int size(){ return n; } class Iter implements Iterator{ int i = 0; @Override public Integer next(){ return dense[i++]+low; } @Override public boolean hasNext(){ return i < n; } @Override public void remove(){ IntSparseSet.this.remove(dense[i - 1] + low); } } @Override public Iterator iterator(){ return new Iter(); } } ```