PAT-Hashing (25)

题目来源Hashing (25)题面点击链接自行查看注意点哈希探测用正向平方探测二次探测通常的平方探测是先加后减这里只用正增量就不用减思路简介素数筛二分查找确定表长之后模拟哈希平方探测即可当然直接一个一个找素数也是可以的你问我为什么用素数筛当然是因为帅素数筛不难写同时效率更高个人觉得如果了解素数筛的话其实写代码的难度跟朴素找素数差不多当然考试的时候会写朴素找就行了遇到的问题哈希平方探测的增量上限是表长table.size()超过表长的话取模后相当于再次从 0 开始增加代码/** * https://www.nowcoder.com/pat/5/problem/4308 * 找素数 */#includebits/stdc.husingnamespacestd;constintN1e4100;intk0;//欧拉筛记录素数的个数vectorintprime(N,0),vis(N,0);voidEuler_sieve(){for(inti2;iN;i){if(!vis[i])prime[k]i;for(intj0;jki*prime[j]N;j){vis[prime[j]*i]1;//筛掉合数if(!(i%prime[j]))break;/* i是prime[j]的倍数时 说明后面的含有prime[j]的因子合数已经被筛选掉 不用重复筛选退出 */}}}voidsolve(){Euler_sieve();intMsize,n;cinMsizen;inttlower_bound(prime.begin(),prime.begin()k,Msize)-prime.begin();Msizeprime[t];vectorinthash(Msize,0);for(inti0;in;i){intk,j;cink;for(j0;jMsize;j){intpos(kj*j)%Msize;if(hash[pos])continue;hash[pos]1;coutpos;break;}if(jMsize)cout-;if(i!n-1)cout ;}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in(in.txt,ios::in);cin.rdbuf(in.rdbuf());intT1;//cinT;while(T--){solve();}return0;}