有（晒素数+枚举）

有

时间限制: 1 Sec  内存限制: 128 MB

题目描述

乌龟给自己的贵重物品上了密码锁。密码锁上有5个数字拨盘。每个数字拨盘每次向上拨使数字增加1(9向上拨得到0)，向下拨使数字减少1(0向下拨得到9)。

拨盘上的数字组成一个5位数。只要拨盘上的数字变为素数，密码锁就会被解开。素数(又称质数)是只能被1和它自身整除的大于1的自然数。因为乌龟动作实在太慢，他希望你帮他计算如何开锁，使得拨动的总次数最少。
 

输入

一个5位数，表示拨盘的初始数字

输出

一个5位素数，表示开启密码锁使用的素数(拨动次数最少)。如有多组解，输出满足条件的最大数

样例输入

复制样例数据

01212

样例输出

01213

1.首先算出2~100000的所有素数。（随便你用什么算法，保证小于等于O(nlogn)就行） 2.其次枚举每一个素数，与原来的数的每一位比较，算出每一位至少要拨几次，然后算出最小的，等于的话，为最大的素数。。

PS：0拨到9有2中方法，分别为拨一次和拨9次，发现没有0-9+10=1,9-0=9; 再来，8拨到2有2中方法，分别为拨4次和拨6次，8-2=6，2-8+10=4； 知道了怎么求每一位的最小拨动次数了吧！

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int prim[9600], vis[100005], tot, num[6], nu[6];
char s[6];

void get_prim(){
	for (int i = 2; i < 100000; i++){
		if(!vis[i]) prim[tot++] = i;
		for (int j = 0; j < tot && prim[j] * i < 100000; j++){
			vis[prim[j] * i] = 1;
			if(i % prim[j] == 0) break;
		}
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	get_prim();
	scanf("%s", s);
	for (int i = 0; i < 5; i++) num[i] = s[i] - '0';
	int tim = 0x3f3f3f3f, ans;
	for (int i = 0; i < tot; i++){
		int cnt = 4, t = prim[i], w = 0;
		while(t){
			nu[cnt--] = t % 10;
			t /= 10;
		}
		while(cnt >= 0) nu[cnt--] = 0;
		for (int i = 0; i < 5; i++){
			int t1 = nu[i] - num[i], t2 = num[i] - nu[i];
			if(t1 < 0) t1 += 10;
			if(t2 < 0) t2 += 10;
			w += min(t1, t2);
		}
		if(tim >= w){
			tim = w;
			ans = prim[i];
		}
	}
	int t = ans, cnt = 0;
	while(t) cnt++, t /= 10;
	for (int i = 1; i <= 5 - cnt; i++) printf("0");
	printf("%d\n", ans);

	return 0;
}
/**/