Conversione di numeri primi

Question

Eventuali duplicati:
Help with algorithm problem from SPOJ

sono imbattuto in questa domanda intervista. Dati due numeri primi di n cifre, converti il ​​primo numero primo nella seconda cifra che cambia una alla volta. Anche i numeri intermedi devono essere primi. Questo deve essere fatto nel numero minimo di passaggi (il controllo della primalità e la modifica di una cifra sono considerati passaggi)

E.g. convertire da 1033 a 8179 (1033-> 1733-> 3733 -> .......-> 8179)

Answer 1

bella sfida per un piovoso Lunedi sera (è qui, comunque!). Questo può essere fatto usando Dijkstra's algorithm. Il primo passo è creare uno graph contenente tutti i numeri primi a 4 cifre. Quindi utilizzare l'algoritmo di Dijkstra per trovare il percorso più breve tra i primi/fine primi. Ecco un'implementazione in 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 

Answer 2

Questo è (un caso speciale di) il problema del percorso più breve. Stai cercando un percorso minimo tra due vertici specificati, attraverso il grafico in cui i vertici sono i primi ei vertici sono collegati da un bordo se e solo se differiscono esattamente di una cifra quando espressi nella base 10. Tutti i bordi hanno un peso 1.

In assenza di una migliore idea per la particolare struttura di questo caso speciale: per 4 cifre questo può sicuramente essere completato in un tempo trascurabile con il tuo algoritmo di ricerca del percorso preferito.

Modifica: oops, ho appena notato che "controllare la primalità" è un passo.

Non capisco più la domanda. Quanti numeri devi "controllare la primalità" per produrre la catena 1033 -> 1733 -> 3733? Se utilizzo un setaccio per trovare tutti i numeri primi meno di 10000, quanti "passaggi" ha preso?

Answer 3

L'approccio migliore è probabilmente depth-first search with iterative deepening, poiché è richiesto il numero minimo di passaggi. La profondità iniziale sarebbe il numero di cifre che sono differenti tra i due numeri.

Answer 4

Questo può essere pensato come un problema grafico. Vorrei provare qualcosa in questo modo:

• Generare tutti i numeri primi di cifre a N (P) senza il valore di partenza iniziale (A) e l'estremo finale (B).
• Calcola la distanza da A a tutti P, scegli quelli che hanno la distanza 1, impostali come figli di A.
• Ripeti fino a quando tutti i numeri primi di P sono stati inseriti nel grafico o è stato trovato un percorso verso B .
• Prendere il percorso più breve da A a B.