普里姆算法是近似求解算法,所以用bfs(宽度优先搜索)算法来解答本题就可以,大概流程如下:
西普CTF-普里姆路径-以夕阳落款
# -*- coding: utf8 -*-
# author:pcat
# http://pcat.cnblogs.com
import gmpy2

#节点,包含元素和步数
class node:
	def __init__(self,element,step):
		self.element=element
		self.step=step

#使用bfs(宽度优先搜索)
def foo():
	start=1373
	end=8017
	Queue=[node(start,0)]
	visited=[start]
	while len(Queue)!=0:
		now=Queue[0]
		del Queue[0]
		if now.element==end:
			return now.step
		for i in xrange(4):
			for j in xrange(10):
				if i==0 and j==0:
					continue
				#得到一个新的四位数
				tmp=int(str(now.element)[:i]+str(j)+str(now.element)[i+1:])
				#判断是否素数,这里用gmpy2库来判断而已
				if gmpy2.is_prime(tmp):
					#该数是否被访问过
					if tmp not in visited:
						visited.append(tmp)
						Queue.append(node(tmp,now.step+1))
	return False

if __name__ == '__main__':
	print foo()
	print 'ok'

Flag:

温馨提示: 此处内容需要评论本文后刷新才能查看,支付2元即可直接查看所有Flag。

小广告:关于获取西普实验吧所有Writeup请点击这里查看索引

查看所有Flag需要付费,需要获取所有Flag的童鞋请访问这里成为付费用户,可以自助把自己的注册邮箱加入网站白名单,即可免回复看到本站所有Flag

Flag大全地址:所有Flag

PS:本站不是实验吧的官方站点,纯粹是个人博客,收取Flag费用仅是维持服务器费用,做站不易,且行窃珍惜,如果喜欢我的博客,愿意捐赠的,可以扫描下面的二维码

微信二维码:
支付宝二维码: