转换素数

Question

可能重复:
帮助SPOJ中的算法问题

遇到了这个面试问题.给定两个n位素数,将第一个素数转换为第二个一次改变一个数字.中间数字也需要是素数.这需要以最少的步骤完成(检查素数和更改数字被视为步骤)

例如,将1033转换为8179(1033-> 1733-> 3733 - > .......-> 8179)

Answer 1

对于一个下雨的周一晚上来说，这是一个很好的挑战（无论如何，它就在这里！）。这可以使用Dijkstra 算法来完成。第一步是创建一个包含所有 4 位素数的图。然后使用 Dijkstra 算法找到起始/结束素数之间的最短路径。这是 Python 中的一个实现：

#! /usr/bin/python -tt

# run as: findpath start end

import sys

(start, end) = map(int, sys.argv[1:3])

# http://primes.utm.edu/lists/small/10000.txt
f = open("10000.txt", "r")
lines = f.readlines()
f.close
lines = lines[4:-1] # remove header/footer
all = "".join(lines) # join lines
all = all.split()
all = map(int, all)

# only want the 4-digit primes
fourdigit = [p for p in all if 1000 <= p and p <= 9999]

# returns digits in a number
digits = lambda x: map(int, str(x))

# cache of digits for each prime
digits_for_nums = {}

# returns digits in a number (using cache)
def digits_for_num(x):
    global digits_for_nums
    if x not in digits_for_nums:
        digits_for_nums[x] = digits(x)
    return digits_for_nums[x]

# returns 1 if digits are same, 0 otherwise
diff = lambda pair: 1 if pair[0] == pair[1] else 0

# computes number of identical digits in two numbers
def distance(a, b):
    pair = (a, b)
    pair = map(digits_for_num, pair)
    pair = zip(pair[0], pair[1])
    pair = map(diff, pair)
    same = sum(pair)
    return same

# adjacency list representation of graph of primes
edges = {}

# construct graph
for a in fourdigit:
    edges[a] = []
    for b in fourdigit:
        if distance(a, b) == 3:
            edges[a].append(b)

infinity = sys.maxint

def smallest():
    global dist, Q
    minimum = infinity
    which = None
    for v in Q:
        if dist[v] <= minimum:
            which = v
            minimum = dist[v]
    return which

# Dijkstra's algorithm
dist = {}
previous = {}
Q = edges.keys()
for v in Q:
    dist[v] = infinity
    previous[v] = None
dist[start] = 0
while len(Q) > 0:
    u = smallest()
    if dist[u] == infinity:
        break
    Q.remove(u)
    for v in edges[u]:
        alt = dist[u] + 1
        if alt < dist[v]:
            dist[v] = alt
            previous[v] = u

# get path between start/end nodes
num = end
path = [num]
while num != start:
    num = previous[num]
    path.insert(0, num)
print path