懒得用线性筛和埃氏筛

详细请见题解 - 【苏州NOI】d029: 求出2－100000之间的所有质数（素数） - TZHSOJ

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

int n;

int pow(int x, int y, int z) {
    int res = 1;
    for(; y; y >>= 1) {
        if(y & 1) res = (res % z * x % z) % z;
        x = (x % z * x % z) % z;
    }
    return res;
}

int MillerRabin(int x) {
    int q = x - 1, k = 0;
    while(!(q & 1)) {
        q >>= 1;
        k++;
    }
    int a = rand() % (x - 2) + 2;
    if(pow(a, q, x) == 1) return 1;
    for(int i = 0; i < k; i++) {
        if(pow(a, q, x) == x - 1) return 1;
        q <<= 1;
    }
    return 0;
}

int test(int x) {
	if(x == 2) return 1;
    for(int i = 1; i <= 10; i++) {
        if(!MillerRabin(x)) return 0;
    }
    return 1;
}

int main()
{
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) {
    	if(test(i)) printf("%d\n", i);
	}
    return 0;
}