lunedì 19 dicembre 2011

1579 è un numero primo?

 Salve!

Un numero primo è un numero maggiore di 1, divisibile solamente per 1 e per sé stesso.

Ecco uno script semplice semplice che "scova" i numeri primi. :)

#!/bin/bash
#bit3lux
read -p "dammi un numero " a
c=2
until [ $c -ge $a ]; do
      b=$(($a % $c))
      if [ $b -eq 0 ]; then
          echo "$a non è un numero primo"
          exit 1
      fi
      c=$(($c+1))
done
echo "$a è un numero primo"
exit 0


ecco alcuni esempi di output:

 [bit3lux@archbang Script]$ bash numberone.sh
dammi un numero 49
49 non è un numero primo

 [bit3lux@archbang Script]$ bash numberone.sh
dammi un numero 101
101 è un numero primo

 [bit3lux@archbang Script]$ bash numberone.sh
dammi un numero 1579
1579 è un numero primo

Per capire come funziona lo script basta fare così:

$ bash -x numberone.sh

Un esempio:

[bit3lux@archbang Script]$ bash -x numberone.sh
+ read -p 'dammi un numero ' a
dammi un numero 49
+ c=2
+ '[' 2 -ge 49 ']' #49 non è divisibile per 2
+ b=1              #il resto è, in questo caso, uguale a 1
+ '[' 1 -eq 0 ']'
+ c=3
+ '[' 3 -ge 49 ']' #non è divisibile per 3.
+ b=1               #resto della divisione è uguale a 1
+ '[' 1 -eq 0 ']'
+ c=4  
+ '[' 4 -ge 49 ']' #non è divisibile per 4.
+ b=1              #resto della divisione è uguale 1
+ '[' 1 -eq 0 ']'
+ c=5
+ '[' 5 -ge 49 ']' #non è divisbile per 5
+ b=4              #in questo caso il resto della divisione è uguale a 4
+ '[' 4 -eq 0 ']'
+ c=6
+ '[' 6 -ge 49 ']'
+ b=1
+ '[' 1 -eq 0 ']'
+ c=7
+ '[' 7 -ge 49 ']'  #49 è divisibile per 7, quindi non è un numero primo
+ b=0                # il resto, infatti, è uguale a 0
+ '[' 0 -eq 0 ']' 

+ echo '49 non è un numero primo'

Come si può capire, il metodo che ho usato nello script è quello di controllare che il numero scelto non sia divisibile per nessun numero minore di n; dove n è sempre il numero scelto :D Es. Posso dire che 11 è un numero primo se, e solo se,  non è divisibile per nessun numero compreso tra 2 e 10.

Vi lascio con una tabella di numeri primi (che, tra l'altro, sono infiniti)



Ciao :)

6 commenti:

  1. Ottimo. Ormai riesci a fare tutto con il/la shell!
    (A proposito facciamo un referendum per stabilirne il genere?)
    Poi, volendo, ci sarebbe il comando factor...

    RispondiElimina
  2. @Juhan
    Tutto? Magari...le cose difficili no :D Bello sarebbe fare uno script che generi segmenti di numeri primi, cioè numeri primi compresi tra due numeri scelti dall'utente. :) Da provare.

    RispondiElimina
  3. Ecco qui il pensiero di @Bit3Lux trasformato a script:

    #!/bin/bash
    #Autore Originale: Bit3lux
    #Modifiche alternative: Lightuono


    c=2
    d=0
    i=0
    primi=()
    non_primi=()

    while [ $a -gt $b ]; do
    read -p "dammi un primo numero: " a
    read -p "dammi un secondo numero: " b

    if [ $b -lt $a ]; then
    echo -e "\nIl SECONDO numero deve essere più grande del PRIMO numero!\n"
    fi
    done

    while [ $a -le $b ]; do

    c=2
    while [ $a -gt $c ]; do
    if [ $((a % c)) -eq 0 ]; then
    d=1
    #exit 0
    fi
    c=$((c+1))
    done

    if [ $d -eq 0 ]; then
    primi[$i]=$a
    i=$((i+1))
    else
    non_primi[$i]=$a
    i=$((i+1))
    fi
    a=$((a+1))
    d=0
    done

    echo -e "\nNUMERI PRIMI: \n ${primi[@]}"

    echo -e "\nNUMERI NON PRIMI: \n ${non_primi[@]}"

    exit 0




    Ps.: Per calcolare i numeri primi da 2 a 1579 ha impiegato 1'26'' :D

    RispondiElimina
  4. Ciao

    La frase:
    "Posso dire che 11 è un numero primo se, e solo se, non è divisibile per nessun numero compreso tra 2 e 10."
    Può essere corretta dicendo che un numero è primo se e solo se non è divisibile per nessun numero compreso fra 2 e 6, ovvero fra 2 e la metà (arrotondata per eccesso) di se stesso.
    Questo perché qualsiasi numero superiore alla metà del numero da controllare darà un valore compreso fra 1 (se stesso) e 2 (la sua metà) e quindi non sarà un numero intero.
    E' il modo più semplice per velocizzare il calcolo e diminuire le interazioni.
    Detto questo poi ci sono altri sistemi per ridurre le iterazioni.
    Ad esempio si possono escludere tutti i numeri pari perché è già stato provato il 4.
    Si possono escludere i numeri multipli ci 3 perché è testato il 3, se un numero è divisibile per 9 lo è anche per 3.
    Quindi, in buona sostanza, si può testare se un numero è primo verificando che non sia divisibile per alcun numero primo precedente alla sua metà.
    ^___^

    RispondiElimina
  5. @LordMax
    Ma grazie! Farò tesoro di ciò che hai scritto. Quando finisco di lavorare, mi applicherò :))

    RispondiElimina