Topic: Aiuto per esercizio numeri primi troncabili  (Letto 896 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Lello0010

  • python unicellularis
  • *
  • Post: 6
  • Punti reputazione: 0
    • Mostra profilo
Aiuto per esercizio numeri primi troncabili
« il: Dicembre 30, 2016, 15:29 »
Salve, sono nuovo del forum e chiedo scusa se ho sbagliato sezione per postare.
Premetto che sono un principiante, comunque avrei bisogno di aiuto per un esercizio che mi è stato assegnato a scuola. Praticamente devo creare un programma che calcoli la somma degli 11 primi troncabili da destra e sinistra, che sono numeri primi che hanno la particolarità che levando una cifra alla volta sia da destra e da sinistra si formano nuovamente numeri primi. Gli 11 numeri sono: 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797 e 739397. Il programma lo ho creato e funziona.
l=0
tronca=0
d=0

for numero in range(11,800000,2):
  l=len(str(numero))
  resti=[]
  while l>0:
    c=str(numero)
    b=int(c[0:l])
    if b==1:
      break
    for n in range(2,b//2+1):
      resti.append(b%n)
    if 0 in resti:
      break
    else:      
      if len(str(b))!=1:
        l=l-1
        continue
      else:
        resti=[]
        l=0
        while l<len(str(numero)):
          c=str(numero)
          b=int(c[l:len(c)])
          if b==1:
            break
          for r in range(2,(b//2)+1):
            resti.append(b%r)
          if 0 in resti:
            break
          else:
            if len(str(b))!=1:
              l=l+1
              continue
            else:
              d=d+numero
              break          
        break
print(d)        
     

 Il problema è che l'ultimo numero primo troncabile  è molto elevato e il mio script che deve analizzare numero per numero ci mette una vita per arrivarci.
Come potrei velocizzarlo?
Grazie in anticipo
« Ultima modifica: Dicembre 30, 2016, 16:09 da Lello0010 »

Offline RicPol

  • python sapiens sapiens
  • ******
  • Post: 3.020
  • Punti reputazione: 9
    • Mostra profilo
Re: Aiuto per esercizio numeri primi troncabili
« Risposta #1 il: Dicembre 30, 2016, 18:09 »
Ciao,
per prima cosa quando inserisci del codice nel forum usa il pulsante "#" per formattarlo, in modo da renderlo più leggibile.

Seconda cosa...
> creare un programma che calcoli la somma degli 11 primi troncabili
> Gli 11 numeri sono: 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797 e 739397

beh, allora il programma è semplice, direi:
[codice]
def f():
  return 23 + 37 + 53 + 73 + 313 + 317 + 373 + 797 + 3137 + 3797 + 739397
[/codice]

Forse quindi volevi dire: "devo scrivere un programma che TROVA i primi 11 etc etc, e quindi ne calcola la somma. Giusto?

Ora, il codice che hai scritto è un po' complicato da leggere, e non ho tempo di vedere che cosa fa davvero. Ma ti consiglio comunque di ripartire da capo.

Il problema si divide in due problemi:

Primo, trovare i numeri primi.
Secondo, controllare che un numero primo sia troncabile
    2a) se sia troncabile da destra
    2b) se sia troncabile da sinistra
Una volta trovati i primi 11 troncabili, ovviamente fare la somma non è poi troppo difficile (immagino).

Ora, il SECONDO dei due problemi è banale. Siccome quando tronchi un numero ottieni per forza un numero inferiore, sicuramente sarà un numero che hai già controllato se è primo oppure no. Mi spiego meglio. Mettiamo che tu abbia già risolto il primo problema: allora avrai una lista di numeri primi che hai trovato. A questo punto controlli ciascuno di questi numeri primi, più o meno con un codice che fa questo:
[codice]
numeri_primi = [2, 3, 5, 7, .... la lista che hai già trovato]

def controllo_se_un_numero_primo_e_troncabile_da_destra(numero):
    fino a quando il numero non è completamente consumato:
        tolgo una cifra da destra
        se il numero che resta è compreso in numeri_primi:
            continue
        altrimenti:
            return False
    return True # il numero è consumato e tutti i suoi sotto-numeri sono primi: vittoria!

def controllo_se_un_numero_primo_e_troncabile_da_sinistra(numero):
    stessa cosa, ma togliendo le cifre da sinistra

def trovo_i_primi_troncabili():
    primi_troncabili = []
    per ciascun numero della lista numeri_primi:
        if (controllo_se_un_numero_primo_e_troncabile_da_destra(numero) and
                controllo_se_un_numero_primo_e_troncabile_da_sinistra(numero)):
            primi_troncabili.append(numero)
    return primi_troncabili
[/codice]

Ora, prova ad implementare in pratica queste funzioni, non dovrebbe essere difficile. Naturalmente questi sono gli algoritmi più banali e sicuramente è possibile ottimizzarli, ma dovrebbero bastare.

Per quanto riguarda il primo problema... Mah, in realtà ovviamente ci sono molti algoritmi molto efficienti per trovare i numeri primi. Il fatto è che i numeri che interessano a te sono talmente piccoli che anche un algoritmo molto inefficiente basta e avanza.
Puoi implementare un crivello di Eratostene, per esempio. Trovi il pseudocodice qui: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. Oppure prova con il test di primalità che trovi qui in pseudocodice: https://en.wikipedia.org/wiki/Primality_test. Entrambi gli algoritmi sono troppo lenti per trovare numeri primi grandi, ma per il tuo range funzionano benissimo.

« Ultima modifica: Dicembre 30, 2016, 18:11 da RicPol »

Offline Lello0010

  • python unicellularis
  • *
  • Post: 6
  • Punti reputazione: 0
    • Mostra profilo
Re: Aiuto per esercizio numeri primi troncabili
« Risposta #2 il: Dicembre 30, 2016, 18:36 »
Grazie mille della risposta davvero esauriente, si il programma comunque li doveva trovare i primi troncabili non mi ero spiegato.
Quando ho tempo traduco la tua risposta e  provo come va.
Grazie ancora.

Offline Lello0010

  • python unicellularis
  • *
  • Post: 6
  • Punti reputazione: 0
    • Mostra profilo
Re: Aiuto per esercizio numeri primi troncabili
« Risposta #3 il: Gennaio 09, 2017, 19:22 »
Oggi ho avuto un' pò di tempo e ho tradotto il tuo pseudocodice, ecco cosa è uscito:
[codice]primi=[]
d=0
def is_not_prime(number):
  for n in range(2,(number//2)+1):
    if number%n==0:
      return True
    else:
      continue
      return False
def troncabile_right_to_left(number):
  l=len(str(number))
  while l>0:
    c=str(number)
    b=int(c[0:l])
    if b==1:
      return False
    if b not in primi:
      if is_not_prime(b):
        return False
      else:
        primi.append(b)
        if len(str(b))==1:
          return True
        else:
          l=l-1
          continue
    else:
      if len(str(b))==1:
       return True
      else:
        l=l-1
        continue

def troncabile_left_to_right(number):
  l=0
  while l<len(str(number)):
    c=str(number)
    b=int(c[l:len(c)])
    if b==1:
      return False
    if b not in primi:     
      if is_not_prime(b):
        return False
      else:
        primi.append(b)
        if len(str(b))==1:
          return True
        else:
          l=l+1
          continue
    else:     
      if len(str(b))==1:
         return True
      else:
         l=l+1
         continue       
def both_troncabile(number):
  if troncabile_left_to_right(number) and troncabile_right_to_left(number):
    return True
  else:
    return False
for numero in range(23,739398,2):
  if both_troncabile(numero):
    d=d+numero
    print(d)
  else:
    continue
[/codice]
Con questo codice in una notte è riuscito a finire il calcolo visto che non analizza i numeri gia analizzati.
Cosa ne pensi?

Offline RicPol

  • python sapiens sapiens
  • ******
  • Post: 3.020
  • Punti reputazione: 9
    • Mostra profilo
Re: Aiuto per esercizio numeri primi troncabili
« Risposta #4 il: Gennaio 09, 2017, 22:22 »
Non ci siamo proprio.

L'idea che ci ti avevo proposto era:
primo, implementa alla buona un algoritmo qualsiasi beccato su internet per trovare i primi... ma quello che hai fatto tu è veramente ma veramente ma veramente alla buona. Ci mette un tempo semplicemente mostruoso.

secondo, usa quell'algoritmo per farti una lista dei primi sotto il milione. Siccome sono tutto sommato pochi, non è un gran danno portarsi in giro la lista per i calcoli successivi. Invece tu ti metti a chiamare il tuo (pessimo) algoritmo a ogni passaggio, sei panato.

Quindi, primo implementa un algoritmo almeno un po' decente per trovare i primi. Quello che ti ho linkato da wikipedia va benissimo. Secondo, usalo per trovare la lista dei primi, una volta per tutte.

A questo punto, il problema dei troncati. Hai avuto l'intuizione giusta, ovvero trasformare il numero in una stringa e depennare una cifra alla volta. Poi però la realizzazione è molto pasticciata. Guarda che è semplicissimo:

a) tolgo una cifra
b) verifico se il numero risultante sta nella lista dei primi (che saggiamente ABBIAMO GIA' CALCOLATO)
     c1) se non c'è, esco subito (return False)
     c2) se c'è, torno al punto a
d) quando ho tolto anche l'ultima cifra, return True.

Questo, implementato due volte: a destra, e a sinistra.

Quindi, il tuo codice deve funzionare così:
[codice]
def is_prime(x):
    # implementa alla brutta un algoritmo

PRIMES = [str(i) for i in range(1000000) if is_prime(i)]  # str(i), piccola furbizia

def is_truncated_left(x):  # mi aspetto già che x sia una stringa!
    tolgo una cifra
    x in PRIMES ?
          no -> return False
          si -> tolgo una cifra e procedo
    return True

def is_truncated_right(x):
    come sopra

truncates = [i for i in PRIMES if is_truncated_left(x) and is_truncated_right(x)]
print (sum([int(i) for i in truncates])  # int(i), perché ovviamente hai delle stringhe adesso...
[/codice]

Chiaro? Ci ho messo solo una piccola astuzia: siccome le funzioni "truncated" lavorano con le stringhe, tanto vale trasformare subito tutti i primi trovati in stringhe, invece di farlo uno a uno all'interno delle funzioni "truncated".

Ora, non dico che queste funzioni "truncated" siano OTTIMIZZATE. Ma inizia a implementarle bene, poi ne discutiamo.
« Ultima modifica: Gennaio 09, 2017, 22:25 da RicPol »

Offline Lello0010

  • python unicellularis
  • *
  • Post: 6
  • Punti reputazione: 0
    • Mostra profilo
Re: Aiuto per esercizio numeri primi troncabili
« Risposta #5 il: Gennaio 09, 2017, 23:00 »
Sì io volevo risolverlo con un algoritmo creato completamente da me però in effetti il mio algoritmo per la ricerca dei primi é imbarazzante ahahaaha.
Comunque grazie mille dei consigli.

Offline RicPol

  • python sapiens sapiens
  • ******
  • Post: 3.020
  • Punti reputazione: 9
    • Mostra profilo
Re: Aiuto per esercizio numeri primi troncabili
« Risposta #6 il: Gennaio 10, 2017, 09:57 »
Sì ma anche il resto però.
Per quanto riguarda i primi, non devi cercare di costruirtelo da solo, l'algoritmo. Non sono cose che si ri-scoprono a partire da zero. O conosci le proprietà dei numeri primi, sei già familiare con gli algoritmi standard, oppure se non hai quelle basi matematiche non c'è niente di male a dare una scorsa a wikipedia. Io non è che proprio ci vado pazzo, per questi problemi a base di algoritmi matematici da ottimizzare. Siccome non ho le basi necessarie, finisco sempre per annoiarmi. Però se devo risolverne uno mi informo in giro, chiaro. Non è che provo un po' a tentoni a mettere insieme qualcosa.