整型关键字的平方探测法散列 (25分)

本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 H(key)=key%TSize，其中 TSize 是散列表的表长。要求用平方探测法（只增不减，即H(Key)+i​²​​ ）解决冲突。

注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。

输入格式：
首先第一行给出两个正整数 MSize（≤10​⁴​​ ）和 N（≤MSize），分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数，数字间以空格分隔。

输出格式：
在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 -。输出间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

4 4
10 6 4 15

输出样例：

0 1 4 -

#include <iostream>
using namespace std;
int N, M, x, flag = 0;
int v[20005];

int isPrime(int x) {
	for (int i = 2; i <= (int)sqrt(x); ++i)
		if (x % i == 0)
			return 0;
	return 1;
}

void Insert(int x) {
	for (int i = 0; i < M; ++i) 
		if (v[(x  + i * i) % M] == 0) {
			v[(x  + i * i) % M] = x;
			cout << (x  + i * i) % M;
			return;
		}
	cout << "-";
}

int main() {
	cin >> M >> N;
	M = max(M, 2);
	while (!isPrime(M))
		M++;
	for (int i = 0; i < N; ++i) {
		cin >> x;
		cout << (i ? " " : "");
		Insert(x);
	}
	return 0;
}