import java.util.LinkedList;
import java.util.concurrent.LinkedBlockingDeque;

public class Primes {
private long timeout = System.nanoTime();
LinkedList<Integer> lprimes = new LinkedList<Integer>();
LinkedList<Integer> lnums = new LinkedList<Integer>();
public long getTimeout() {
    return timeout;
}

public void setTimeout(long timeout) {
    this.timeout = timeout;
}

public int getCountPrimes(){
    return this.lprimes.size();
}
public void timeRun() {
    System.out.println(System.nanoTime());
    System.out.println(timeout);
    System.out.println("Время выполнения равно " + String.valueOf(System.nanoTime() - this.timeout)+" ns или " + String.valueOf((System.nanoTime() - this.timeout)/1000000));
}

public void keepPrimes() {
    lnums.add(2);
    for(int i = 3;i <= 10000;i += 2){
           lnums.add(i);
    }
    /*for (int i = 2; i <= 10000; i++) {
        lnums.add(i);
    }*/
    while(lnums.size()>0){
        int nextPrime = lnums.remove();
        for (int i = nextPrime*nextPrime; i <=10000; i+=nextPrime) {
            lnums.removeFirstOccurrence(i);
        }
        lprimes.add(nextPrime);
        System.out.println(nextPrime);
    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println("Максимальное значение INT: "+Integer.MAX_VALUE);
    Primes primes = new Primes();
    primes.keepPrimes();
    System.out.println("Формирование коллекции закончено!");
    primes.timeRun();
    System.out.println(primes.getCountPrimes());
}

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#define lim INT32_MAX
#define BITS 32
int main()
{
    uint32_t *x= calloc(sizeof*x, ((unsigned)lim-3+BITS*2-1)/(BITS*2));
    fputs("2n", stdout);
    for(unsigned i=3;i<=lim;i+=2) {
        unsigned b= i-3 >> 1;
        if(x[b/BITS] & 1<<b%BITS) continue;
        printf("%dn", i);
        while( (b+=i) <= (lim-3>>1) ) x[b/BITS] |= 1<<b%BITS;
    }
}

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#define lim INT32_MAX
#define BITS 32
int main()
{
    uint32_t *x= calloc(sizeof*x, ((unsigned)lim-5+BITS*3-3)/(BITS*3));
    fputs("2n3n", stdout);
    for(unsigned i=5, b0=0; i<=lim; i+=6, b0++) {
        unsigned b=b0;
        if(!( x[b/(BITS/2)] & 1<<b%(BITS/2)*2 )) {
            printf("%dn", i);
            while( (b+=i) <= (lim-5)/6 ) x[b/(BITS/2)] |= 1<<b%(BITS/2)*2;
            for(b=b0+2*i/3; b <= (lim-5)/6; b+=i) x[b/(BITS/2)] |= 2<<b%(BITS/2)*2;
        }
        b=b0;
        if(!( x[b/(BITS/2)] & 2<<b%(BITS/2)*2 )) {
            printf("%dn", i+2);
            while( (b+=i+2) <= (lim-5)/6 ) x[b/(BITS/2)] |= 2<<b%(BITS/2)*2;
            for(b=b0+2*i/3+2; b <= (lim-5)/6; b+=i+2) x[b/(BITS/2)] |= 1<<b%(BITS/2)*2;
        }
    }
}

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

constexpr inline unsigned long pow2(unsigned long i) { return 1 << i; }

unsigned long isqrt(unsigned long a)
{
    unsigned long x = a;
    for(unsigned long z = 0; x != z; )
    {
        z = x;
        x = (x + a/x)/2;
    }
    return x;
}

constexpr unsigned long MAX_LIM = pow2(31) - 1;
constexpr unsigned long ARR_LIM = (MAX_LIM >> 6) + 1;
const     unsigned long SQR_LIM = isqrt(MAX_LIM);;

unsigned long primes[ARR_LIM] = { 0 }; // 0 - простое, 1 - составное

auto set_primes = [](unsigned long idx)
    { primes[idx >> 6] |= pow2((idx&0x0000003F)>>1); };
auto get_primes = [](unsigned long idx)
    { return primes[idx >> 6] &  pow2((idx&0x0000003F)>>1); };

int main(int argc, const char * argv[])
{
    for(unsigned long i = 3; i <= SQR_LIM; i += 2)
    {
        if (get_primes(i)) continue;
        for(unsigned long j = i * i; j <= MAX_LIM; j += 2*i)
        {
            set_primes(j);
        }
    }

    puts("2");
    for(unsigned long i = 3; i <= MAX_LIM; i+=2)
    {
        if (get_primes(i)) continue;
        printf("%lun",i);
    }
}