题目粗心：
给出散列表长MSize和欲插入的元素，将这些元素按读入的程序插入散列表中，其中散列函数为H(key)= key %MSize,解决抵触采纳只往正向减少的次探查法(即二次方 探查法)。另外，如果题目给出的MSize不是素数，那么须要将MSize从新赋值为第一个比MSize大的素数再进行元素插入。
算法思路:
间接模仿hash映射的过程，首选对于输出的MSize如果不是素数就找到第一个比它大的素数，而后就对每一个输出的数据进行hash映射，应用pos记录映射的地位，如果hashTable[pos]!=0阐明以后地位存在抵触，那么就应用二次方探测法进行rehash，如果找到空位后退出循环，如果rehash的次数大于或者等于hash表的长度就表明没有适合的空位也退出循环。这里应用step记录以后存在hash抵触的时候rehash的次数。退出循环后判断step是否大于等于MSize，如果是输入"-",否则输入pos,并且将pos对应地位设置为num。最初留神输入空格。判断一个数字N是否为素数的办法如下：
办法一：
依据素数的定义可知，素数是指大于1，且只能被1和它本身整除的自然数。1不是素数。依据乘法的个性，可知若从2开始遍历到被判断数的平方根都没有找到能被整除的数，则这个数肯定为素数。对应代码如下：
bool isPrime(int N){ if(N<=1) return false; for (int i = 2; i <= sqrt(N * 1.0); ++i) { if(N%i==0) return false; } return true;}办法二：
对于一个大于等于5的素数，其特点是总是等于6x-1和6x+1,其中 x 是大于等于1的自然数.那么依据这个特点,失去的论断为,在6的倍数两边的数字不肯定是素数，然而不在6的倍数两边的数字肯定不是素数,这样就能够优化下面的代码，思路就是首先特判小于4的数字，只有2和3才是素数，而后对于所有对6整除余数不为1和5的阐明不在6的倍数的两边，肯定不是素数，最初从5开始，步长为6进行遍历每一个在6两边的数字，对于能够对于6的倍数两边的数字能够整除的肯定不是素数。代码如下：
bool isPrime(int N){ if(N<=3){ return N>1;//2和3才是素数 } if(N%6!=1&&N%6!=5) return false; for (int i = 5; i <= sqrt(N * 1.0); i+=6) { if(N%i==0||N%(i+2)==0) return false; } return true;}对于rehash次数只须要MSize次的证实(思否的公式编辑存在bug,预览的时候没问题，在公布就有乱码了，上面是预览的截图)
留神点：
1、对于测试点0和3谬误的状况，能够认真看看是不是二次方探测的办法写错了，正确写法是pos = (num+step*step)%MSize;而不是pos = (pos+step*step)%MSize;
2、如果二次方探测始终没有找到空位，得应用step管制rehash的次数不超过MSize，否则测试点3超时。
3、如果谬误的判断1也是素数的化，测试点1会出错。
提交后果：
AC代码;
#include <cstdio>#include <cstring>#include <cmath>using namespace std;// 判断N是否为素数//bool isPrime(int N){// if(N<=1) return false;// for (int i = 2; i <= sqrt(N * 1.0); ++i) {// if(N%i==0) return false;// }// return true;//}bool isPrime(int N){ if(N<=3){ return N>1;//2和3才是素数 } // 不在6的倍数两边的数字肯定不是素数 if(N%6!=1&&N%6!=5) return false; for (int i = 5; i <= sqrt(N * 1.0); i+=6) { if(N%i==0||N%(i+2)==0) return false; } return true;}int hashTable[100000] = {};// hash表int main(){ int MSize,N;// hash表的大小和插入的数字个数 scanf("%d %d",&MSize,&N); // 找到第一个大于等于MSize素数 while (true){ if(isPrime(MSize)) break; ++MSize; } int num;// 输出的每一个数字 for (int i = 0; i < N; ++i) { scanf("%d",&num); int pos = num%MSize;// 插入的地位 int step = 1;// 二次探方的步长 while (hashTable[pos]!=0&&step<MSize){ // 存在hash抵触 pos = (num+step*step)%MSize; ++step; } if(step>=MSize){ // 没有空位 printf("-"); } else { printf("%d",pos); hashTable[pos] = num; } if(i<N-1) printf(" "); } return 0;}