Funzione per trovare numeri primi

« Older   Newer »
 
  Share  
.
  1. x-reynik-x
     
    .

    User deleted


    Ho scritto questa funzione per trovare numeri primi, come posso migliorarla secondo voi? 0 = numero primo -1 = numero non primo
    CODICE
    #!/usr/bin/env python
       # -*- coding: utf-8 -*
       
    >>> import math
    >>> a = 0
    >>> c = 2
    >>> l = []
    >>> def IsPrime(n):
           l = int(math.sqrt(n)) + 1
           for a in range (2, 1):
                   if n % a == 0:
                           return -1
           return 0
     
    Top
    .
  2. x-reynik-x
     
    .

    User deleted


    Non funziona! L'ho riscritta completamente in un altro modo, ma ci sono dei problemi anche qui:
    CODICE
    def prime(n):
           if n == 1 or n == 2 or n == 3:
                           print(n, 'è primo')
           elif n % 2 == 0:
                   print(n, 'non è primo')
           else:
                   for x in range(2, int((n/2) + 1)):
                           if n % x == 0:
                                   break
                                   if n % x != 0:
                                           break
                           else:
                                   print(n, 'è primo')


    Il problema è che durante il ciclo for mi scrive se n è divisibile o meno per ogni numero di for, cioè:
    se deve controllare il numero 23 prova tutti i numeri e mi dice per ciascuno se 23 è divisibile. Io vorrei che controllasse solo alla fine, ma non so come si fa, potreste aiutarmi? per piacere
     
    Top
    .
  3. ~{Skydrake™}»
     
    .

    User deleted


    CITAZIONE (x-reynik-x @ 7/11/2009, 16:30)
    potreste aiutarmi? per piacere

    Ci provo.
    Il tuo primo codice mi sembra abbastanza corretto, tranne questa parte
    CODICE
    for a in range (2,1)

    Non conosco il Python, ma non dovrebbe essere
    CODICE
    for a in range (2,l)

    (la l al posto dell'1)?
    Inoltre non c'è bisogno di sommare 1 alla radice del numero.

    Ricapitolando,
    CODICE
    def IsPrime(n):
          l = int(math.sqrt(n))
          for a in range (2, l):
                  if n % a == 0:
                          return -1
          return 0
     
    Top
    .
  4. ~{Skydrake™}»
     
    .

    User deleted


    Ho sempre utilizzato questo metodo, ma adesso ti mostro un esempio ideato da un membro di una community di programmatori, lorelapo.
    CODICE
    primo(n)
    if(n<=3)return true;
    m=2;
    while(m<=(nm))
    {
    if(n%­m==0)return false;
    m++;
    }
    return true

    Il codice dovrebbe essere abbastanza chiaro ;)
     
    Top
    .
  5. ~Andrey™
     
    .

    User deleted


    CITAZIONE (x-reynik-x @ 7/11/2009, 16:30)
    Il problema è che durante il ciclo for mi scrive se n è divisibile o meno per ogni numero di for, cioè:
    se deve controllare il numero 23 prova tutti i numeri e mi dice per ciascuno se 23 è divisibile. Io vorrei che controllasse solo alla fine, ma non so come si fa, potreste aiutarmi? per piacere

    Non ho capito cosa vuoi dire.

    Il return mi pare che faccia uscire dalla funzione, per cui la prima divisione che da resto uguale a zero [numero non primo] fa terminare la funzione restituendo -1. Che senso ha continuare?

    Comunque quoto Ruggy, dovrebbe essere "l" il secondo parametro xD
     
    Top
    .
  6. x-reynik-x
     
    .

    User deleted


    Nel metodo di lorelapo non ho capito cosa significa quel m++
    @andrey: il pezzo che hai citato si riferisce alla seconda funzione, quella subito sopra
     
    Top
    .
  7. ~Andrey™
     
    .

    User deleted


    CITAZIONE (x-reynik-x @ 7/11/2009, 17:30)
    Nel metodo di lorelapo non ho capito cosa significa quel m++
    @andrey: il pezzo che hai citato si riferisce alla seconda funzione, quella subito sopra

    Ma probabilmente la prima non funziona proprio per quell'errore, riprova mettendo "l".
     
    Top
    .
  8. ~{Skydrake™}»
     
    .

    User deleted


    CITAZIONE (x-reynik-x @ 7/11/2009, 17:30)
    quel m++

    m++ equivale a m=m+1
     
    Top
    .
  9.  
    .
    Avatar

    Senior Member

    Group
    Staff
    Posts
    10,796

    Status
    Anonymous
    Sono riuscito a combinare qualcosa

    CODICE
    def primo(n):
     if n%2==0 and n!=2:
       print "Il numero ",n," non e primo"
     elif n==2:
       print n," e primo"
     else:
       for i in range(3,(n+1)):
         if n%­i==0 and n!=i:
           print n," non e primo il suo primo divisore e ",i,""
           break
         elif n%­i==0:
           if n==i:
             print n,"e un numero primo"
             break
     
    numero = input('Inserisci il numero:')
     
    primo(numero)


    è molto simile alla tua, un pò riaggiustata. Se hai bisogno di chiarimenti chiedi, sono qui!! :)
     
    Top
    .
  10. ~{Skydrake™}»
     
    .

    User deleted


    CITAZIONE (RootkitNeo @ 7/11/2009, 22:12)
    Sono riuscito a combinare qualcosa

    CODICE
    def primo(n):
     if n%2==0 and n!=2:
       print "Il numero ",n," non e primo"
     elif n==2:
       print n," e primo"
     else:
       for i in range(3,(n+1)):
         if n%­i==0 and n!=i:
           print n," non e primo il suo primo divisore e ",i,""
           break
         elif n%­i==0:
           if n==i:
             print n,"e un numero primo"
             break
     
    numero = input('Inserisci il numero:')
     
    primo(numero)


    è molto simile alla tua, un pò riaggiustata. Se hai bisogno di chiarimenti chiedi, sono qui!! :)

    Computazionalmente è molto pesante...
    Se non ti va di scervellarti troppo con gli algoritmi, fai semplicemente un ciclo da 2 a radice di N, e se trovi un divisore, il numero non è primo.
     
    Top
    .
  11.  
    .
    Avatar

    Senior Member

    Group
    Staff
    Posts
    10,796

    Status
    Anonymous
    CITAZIONE (~{Skydrake™}» @ 7/11/2009, 22:22)
    Computazionalmente è molto pesante...
    Se non ti va di scervellarti troppo con gli algoritmi, fai semplicemente un ciclo da 2 a radice di N, e se trovi un divisore, il numero non è primo.

    Hai decisamente ragione!! :)

    In quel modo però poteva confrontarlo al suo script visto la similitudine!
    Questo è java

    CODICE
    String isPrime(int n) {
     for(int i=0; i<(int)Math.sqrt(n); i++) {
       if(i%­n==0) stato="Il numero "+n+" non e' primo.";
       else stato = "Il numero "+n+" e' primo.";
     }
     return stato;
    }


    Traducibile tranquillamente in Python! ;)
     
    Top
    .
  12. ~Andrey™
     
    .

    User deleted


    CITAZIONE (RootkitNeo @ 7/11/2009, 22:51)
    CITAZIONE (~{Skydrake™}» @ 7/11/2009, 22:22)
    Computazionalmente è molto pesante...
    Se non ti va di scervellarti troppo con gli algoritmi, fai semplicemente un ciclo da 2 a radice di N, e se trovi un divisore, il numero non è primo.

    Hai decisamente ragione!! :)

    In quel modo però poteva confrontarlo al suo script visto la similitudine!
    Questo è java

    CODICE
    String isPrime(int n) {
     for(int i=0; i<(int)Math.sqrt(n); i++) {
       if(i%­n==0) stato="Il numero "+n+" non e' primo.";
       else stato = "Il numero "+n+" e' primo.";
     }
     return stato;
    }


    Traducibile tranquillamente in Python! ;)

    Sarebbe meno dispendioso fare così:
    CODICE
    String isPrime(int n) {
     for(int i=0; i<(int)Math.sqrt(n); i++) {
       if(i%­n==0) return "Il numero "+n+" non e' primo.";
     }
     return "Il numero "+n+" e' primo.";
    }

    Si risparmiano un sacco di assegnazioni della variabile stato, e un sacco di iterazioni nel caso non fosse primo [in questo modo infatti se non è primo, al primao divisore la funzione termina] :)
     
    Top
    .
  13. x-reynik-x
     
    .

    User deleted


    Grazie! Ora provo a tradurre l'ultimo codice in python!
     
    Top
    .
  14. lumo
     
    .

    User deleted


    CITAZIONE (~Andrey™ @ 7/11/2009, 23:31)
    CITAZIONE (RootkitNeo @ 7/11/2009, 22:51)
    Hai decisamente ragione!! :)

    In quel modo però poteva confrontarlo al suo script visto la similitudine!
    Questo è java

    CODICE
    String isPrime(int n) {
     for(int i=0; i<(int)Math.sqrt(n); i++) {
       if(i%­n==0) stato="Il numero "+n+" non e' primo.";
       else stato = "Il numero "+n+" e' primo.";
     }
     return stato;
    }


    Traducibile tranquillamente in Python! ;)

    Sarebbe meno dispendioso fare così:
    CODICE
    String isPrime(int n) {
     for(int i=0; i<(int)Math.sqrt(n); i++) {
       if(i%­n==0) return "Il numero "+n+" non e' primo.";
     }
     return "Il numero "+n+" e' primo.";
    }

    Si risparmiano un sacco di assegnazioni della variabile stato, e un sacco di iterazioni nel caso non fosse primo [in questo modo infatti se non è primo, al primao divisore la funzione termina] :)

    In teoria si, ma in pratica il compilatore ti ottimizza il codice e lo fa diventare come il tuo xD
    Comunque per funzioni come quella sarebbe meglio tornare a un Boolean ( true, false )
     
    Top
    .
  15. x-reynik-x
     
    .

    User deleted


    CITAZIONE (~{Skydrake™}» @ 7/11/2009, 16:56)
    Ho sempre utilizzato questo metodo, ma adesso ti mostro un esempio ideato da un membro di una community di programmatori, lorelapo.
    CODICE
    primo(n)
    if(n<=3)return true;
    m=2;
    while(m<=(nm))
    {
    if(n%­m==0)return false;
    m++;
    }
    return true

    Il codice dovrebbe essere abbastanza chiaro ;)

    In python l'ho tradotto così ma funziona solo fino a 3: (Guardate anche lo screen che c'è sotto)

    CODICE
    def prime(n):
           if n <= 3:
                   return true
           m == 2
           while m <= (n*m):
                   if n % m == 2:
                           return false
                           m = m + 1
                   return true


     
    Top
    .
44 replies since 3/11/2009, 17:13   3110 views
  Share  
.