C: numero primo

[lucas87]

chi mi scrive un semplice algoritmo per vedere se un numero è primo oppure no?

[VICIUS]

Il piu famoso e anche semplice è il crivello di eratostene. http://it.wikipedia.org/wiki/Crivello_di_Eratostene
Se ti serve un esempio in qualche linguaggio basta chiedere.

ciao

[lucas87]

Il punto è che non mi serve per vedere se una serie di numeri è primi, ma voglio sapere dato n da input, dire se questo è primo. il linguaggio è C.

grAZIE

[ilsensine]

Il modo più semplice è controllare che non sia divisibile per nessuno dei numeri dispari da 3 alla radice quadrata del numero che stai controllando.

Non esistono algoritmi efficienti per risolvere questo problema.

[lucas87]

per questa volta mi posteresti direttamente un algoritmo abbastanza buono per fare quello che ho detto?

[icecube_HU]

Originariamente inviato da ilsensine

Il modo più semplice è controllare che non sia divisibile per nessuno dei numeri dispari da 3 alla radice quadrata del numero che stai controllando.

Non esistono algoritmi efficienti per risolvere questo problema.

Gia' !

Per guadagnare un po' in efficienza, conviene sfruttare il fatto che tutti i numeri primi (tranne 2 e 3) sono della forma: 6*K +/- 1,
calcolando: r = N mod 6
Se r e' diverso da 1 o 5, il numero NON e' primo.
Poi si prosegue come hai indicato...

Ciao !

[lucas87]

Vi sto chiedendo per favore di postarmi direttamente la codifica in C.

graZIE

[mdr268]

te la saprei fare in pascal, ma non in C..

[lucas87]

Allora me la fai in pascal? poi traduco io. grazie tanto

[mdr268]

dammi 10 min..

dopo me lo posti tradotto così mi imparo un po' di C

[icecube_HU]

Originariamente inviato da lucas87

Vi sto chiedendo per favore di postarmi direttamente la codifica in C.
graZIE

Sorry, I don't speak C.

Pero' in VB o VBA e':

Function IsPrime(N As Long) As Boolean
   Dim r As Long
   If N <= 0 Then Err.Raise 5, "IsPrime", "Argomento errato !"
   If N <= 3 Then
      IsPrime = True
   Else
      r = N Mod 6
      If r = 1 Or r = 5 Then
         For r = 3 To Sqr(N) Step 2
            If (N Mod r) = 0 Then Exit Function
         Next
         IsPrime = True
      End If
   End If
End Function

Non dovrebbe esserti troppo difficile tradurlo in C...

Ciao !



EDIT: come giustamente fatto notare, 1 NON E' primo !!
Basterebbe una piccola modifica alla routine, ma a questo punto conviene riscriverla col costrutto Select, piu' efficiente:

Public Function IsPrime(n As Long) As Boolean
   Dim r As Long
   Select Case n
      Case Is < 0: Err.Raise 5, "IsPrime", "Argomento errato !"
      Case 0, 1: 'niente, non sono primi
      Case 2, 3: IsPrime = True
      Case Else
         r = n Mod 6
         If r = 1 Or r = 5 Then
            For r = 3 To Sqr(n) Step 2
               If (n Mod r) = 0 Then Exit Function
            Next
            IsPrime = True
         End If
   End Select
End Function

[mdr268]

avevo quasi finito in pascal, ma visto che ti è arrivata la soluzione in vb lascio quella che è fatta meglio ^^

[lucas87]

Grazie a tutti.

[lucas87]

una sola cosa. cosa vuol dire step 2, che incrementa di 2 il contatore?

[icecube_HU]

Originariamente inviato da lucas87

una sola cosa. cosa vuol dire step 2, che incrementa di 2 il contatore?

Si' !

[mdr268]

potresti incollare la tua traduzione in C? sono curioso di sapere come hai fatto a tradurre l'incremento di 2..

un altra cosa, cosa vuol dire err raise?

[icecube_HU]

Originariamente inviato da mdr268

potresti incollare la tua traduzione in C? sono curioso di sapere come hai fatto a tradurre l'incremento di 2..

un altra cosa, cosa vuol dire err raise?

Genera un errore "Invalid argument" se si calcola la funzione per valori negativi o uguali a zero, per i quali non e' definita.

Lo stesso che avviene, ad esempio, per la funzione standard Log().

[cionci]

Originariamente inviato da mdr268

potresti incollare la tua traduzione in C? sono curioso di sapere come hai fatto a tradurre l'incremento di 2..

i+=2 invece di i++ nel for...

[Ziosilvio]

Originariamente inviato da lucas87

voglio sapere dato n da input, dire se questo è primo

Vuoi sapere tu, o ti ha dato l'esercizio il prof?

[lucas87]

int is_prime(int a){

long r;
if (a==0){
return 0;
}
if (a<=3){
return 1;
}
else {
r=a % 6;
if ((r==1) || (r==5)){
for (r=3;r<=sqrt(a);r=r+2){
if ((a % r) == 0){
return 1;
}
else {
return 0;
}
}

}
}
}


ritorna 1 se è primo, zero se non lo è.