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<Integer> 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<Integer>(primes)) {
System.out.printf("%d ", x);
}
System.out.println();
}
}
class IntSparseSet extends AbstractSet<Integer> {
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<h-l;i++)
{
sparse[i]=99999;
dense[i]=99999;
}
}
@Override
public boolean add(Integer x){
x-=low;
if (sparse[x]>=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<Integer>{
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<Integer> iterator(){
return new Iter();
}
}