PAT1059 C语言竞赛(C语言版本，10ms以内低时间复杂度)

题目链接：PAT1059 C语言竞赛
解题思路：

1. 利用筛选法构造素数数组num[]，下表非素数的值置为0，素数则为1，用于检查奖品。
2. 输入学生的信息，学号，学号用于结构体数组的下标，设置奖品，标志位置为1；
3. 打印显示，需要在小于四位数前面补充0；

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

#define N 10010

//构造结构体，奖品名称，被检查标志位
struct Info{
	char prize[20];
	int checked;
};
struct Info info[N];

//筛法构造素数数组，非素数下标置为0
int num[N];
void initialPrime() {
	int i, j;
	for (i = 0; i < N; i++) {
		num[i] = 1;
	}

	for (i = 2; i < N; i++) {
		if (num[i] == 0) {
			continue;
		} 
		for (j = 2; j * i < N; j++) {
			num[j * i] = 0;
		}
	}
}

int main() {
	int i, n, m;
	int check_num;
	int stu_num;
	initialPrime();
	scanf("%d", &n);
	//输入学生信息
	for (i = 1; i <= n; i++) {
		scanf("%d", &stu_num);
		info[stu_num].checked = 1;
		if (i == 1) {
			strcpy(info[stu_num].prize, "Mystery Award");	
		} else {
			if (num[i] == 1) {
				strcpy(info[stu_num].prize, "Minion");	
			} else {
				strcpy(info[stu_num].prize, "Chocolate");	
			}
		}
	}
	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		scanf("%d", &check_num);
		if (check_num < 10) {
			printf("000");
		} else if(check_num < 100) {
			printf("00");
		} else if (check_num < 1000) {
			printf("0");
		}
		if (strcmp(info[check_num].prize,"") != 0) {
			if (info[check_num].checked == 1) {
				printf("%d: %s\n", check_num, info[check_num].prize);
				info[check_num].checked = 0;
			} else {
				printf("%d: Checked\n", check_num);
			}
		} else {
			printf("%d: Are you kidding?\n", check_num);
		}
	}
	return 0;
}