阳寿做法(不会有人复制这个来尝试AC吧)

#include <cstdio>
#include <stdlib.h>
#include <time.h>

inline int reader(){
	int it = 0 , chr = getchar()  ;
	while('0' > chr || chr > '9')
		chr = getchar();
	while('0' <= chr && chr <= '9')
		it = (it << 1) + (it << 3) + chr - '0' ,chr = getchar() ;
	return it;
} 

int n , q ;

int main(){
	n = reader() ;
    q = reader() ;
    srand(time(NULL));
	//随机数，听天由命
    while(q --)
    	printf("%d\n",rand()%2);
	return 0 ;
}//一个样例都没过

#1	 Wrong Answer 读取到 0，应为 0。	64ms	288 KiB
#2	 Wrong Answer 读取到 1，应为 0。	52ms	320 KiB
#3	 Wrong Answer 读取到 1，应为 0。	18ms	304 KiB
#4	 Wrong Answer 读取到 1，应为 0。	53ms	412 KiB
#5	 Wrong Answer 读取到 1，应为 0。	2ms 	272 KiB
#6	 Wrong Answer 读取到 1，应为 0。	12ms	224 KiB
#7	 Wrong Answer 读取到 1，应为 0。	5ms 	376 KiB
#8	 Wrong Answer 读取到 1，应为 0。	68ms	376 KiB
#9	 Wrong Answer 读取到 1，应为 0。	29ms	248 KiB
#10	 Wrong Answer 读取到 1，应为 0。	28ms	276 KiB

基础做法

#include <cstdio>

inline int reader(){//什么老六题目，卡我时间
	int it = 0 , chr = getchar()  ;
	while('0' > chr || chr > '9')
		chr = getchar();
	while('0' <= chr && chr <= '9')
		it = (it << 1) + (it << 3) + chr - '0' ,chr = getchar() ;
	return it;
} 

int n , q , pi , primes[5761455];
bool unprime[100000001] ;

int main(){
	unprime[0] = unprime[1] = 1;
	n = reader() ;
    //线性筛
    for(int i = 2 ; i <= n ; i ++){
		//遍历
        if(!unprime[i])
			//没筛到是质数
			primes[pi++] = i;	
	    for(int j = 0 ; j <= pi && i * primes[j] <= n; j ++){
	        unprime[i*primes[j]] = 1;
			//筛去合数
	        if(i % primes[j] == 0) break;
			//保证每个数只被筛了一遍
	    }
    }
	//讲的比较简单，可以百度自搜
    q = reader() ;
    while(q --)//输出
    	printf("%d\n" , !unprime[reader()]) ;
	return 0 ;       
}

但是；

#4	 Accepted	962ms	104.5 MiB
#8	 Accepted	991ms	87.8 MiB

很显然，离去世就差几毫秒 所以

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <cstdio>
//pragma优化貌似OI不能用，所以考试时老老实实想别的路

inline int reader(){
	int it = 0 , chr = getchar()  ;
	while('0' > chr || chr > '9')
		chr = getchar();
	while('0' <= chr && chr <= '9')
		it = (it << 1) + (it << 3) + chr - '0' ,chr = getchar() ;
	return it;
} 

int n , q , pi , k , primes[5761455] ;
bool unprime[100000001] ;

int main(){
	unprime[0] = unprime[1] = 1;
	n = reader() ;
    for(int i = 3 ; i <= n ; i += 2){
		//直接对2倍数特判
		//省了一半时间
		if(!unprime[i])
			primes[pi++] = i;
		for(int j = 0 ; j < pi && (i * primes[j]) <= n; j ++){
			unprime[i*primes[j]] = 1;
			if(i % primes[j] == 0) break;
		}
    }
    q = reader() ;
    while(q --){
    	k = reader() ;
		//特判 奇数或2
    	if(k & 1 || k == 2)
    		putchar((!unprime[k]) + '0');
    	else
    		putchar('0') ;
    	putchar('\n') ;
	}
	return 0 ;
}

结果

#1	 Accepted	317ms	69.2 MiB
#2	 Accepted	188ms	31.6 MiB
#3	 Accepted	329ms	100.5 MiB
#4	 Accepted	397ms	105.4 MiB
#5	 Accepted	218ms	71.4 MiB
#6	 Accepted	48ms	12 MiB
#7	 Accepted	365ms	91.1 MiB
#8	 Accepted	423ms	89 MiB
#9	 Accepted	312ms	93.6 MiB
#10	 Accepted	184ms	58.5 MiB
分数100  总耗时2780ms  峰值内存105.4 MiB