lucas87
21-11-2006, 14:44
chi mi scrive un semplice algoritmo per vedere se un numero è primo oppure no?
View Full Version : C: numero primo
VICIUS
21-11-2006, 14:49
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 ;)
Se ti serve un esempio in qualche linguaggio basta chiedere.
ciao ;)
lucas87
21-11-2006, 14:52
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
grAZIE
ilsensine
21-11-2006, 14:59
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.
Non esistono algoritmi efficienti per risolvere questo problema.
lucas87
21-11-2006, 15:03
per questa volta mi posteresti direttamente un algoritmo abbastanza buono per fare quello che ho detto?
icecube_HU
21-11-2006, 15:12
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' ! :D
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 !
Non esistono algoritmi efficienti per risolvere questo problema.
Gia' ! :D
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
21-11-2006, 15:16
Vi sto chiedendo per favore di postarmi direttamente la codifica in C.
graZIE
graZIE
mdr268
21-11-2006, 15:26
te la saprei fare in pascal, ma non in C.. :muro:
lucas87
21-11-2006, 15:27
Allora me la fai in pascal? poi traduco io. grazie tanto
mdr268
21-11-2006, 15:28
dammi 10 min.. :D
dopo me lo posti tradotto così mi imparo un po' di C
dopo me lo posti tradotto così mi imparo un po' di C
icecube_HU
21-11-2006, 15:36
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
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
21-11-2006, 15:40
avevo quasi finito in pascal, ma visto che ti è arrivata la soluzione in vb lascio quella che è fatta meglio ^^
lucas87
21-11-2006, 16:42
Grazie a tutti.
lucas87
21-11-2006, 16:52
una sola cosa. cosa vuol dire step 2, che incrementa di 2 il contatore?
icecube_HU
21-11-2006, 17:59
una sola cosa. cosa vuol dire step 2, che incrementa di 2 il contatore?
Si' ! :)
Si' ! :)
mdr268
21-11-2006, 20:09
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?
un altra cosa, cosa vuol dire err raise?
icecube_HU
22-11-2006, 08:39
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().
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
22-11-2006, 11:06
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...
i+=2 invece di i++ nel for...
Ziosilvio
22-11-2006, 11:22
voglio sapere dato n da input, dire se questo è primo
Vuoi sapere tu, o ti ha dato l'esercizio il prof?
Vuoi sapere tu, o ti ha dato l'esercizio il prof?
lucas87
22-11-2006, 13:57
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 è.
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 è.
Ziosilvio
22-11-2006, 14:34
int is_prime(int a){
Per cortesia: impara a usare il tag "code".
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 è.
La funzione restituisce 1 se l'input è 1; e 1 non è un numero primo.
(Se 1 fosse primo, non sarebbe più vero che ogni intero positivo si scompone in prodotto di numeri primi in modo unico almeno dell'ordine, e questo proprio perché si può moltiplicare per 1 quante volte si vuole.)
Il test su a%6 è reso superfluo dal resto, e non rende significativamente più veloce il programma.
Inoltre, hai dimenticato di specificare la condizione di ritorno in questo caso. (Lo vedi subito dall'indentazione.)
La condizione r<=sqrt(a) equivale a r*r<=a, la quale ha il vantaggio di usare solo int.
I valori di ritorno del test su a%r sono scambiati: se a%r==0, allora a è divisibile per r.
Cosa ancora più grave: il "return 0" sta dentro il ciclo for, col risultato che questo viene eseguito una volta sola.
Per cortesia: impara a usare il tag "code".
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 è.
La funzione restituisce 1 se l'input è 1; e 1 non è un numero primo.
(Se 1 fosse primo, non sarebbe più vero che ogni intero positivo si scompone in prodotto di numeri primi in modo unico almeno dell'ordine, e questo proprio perché si può moltiplicare per 1 quante volte si vuole.)
Il test su a%6 è reso superfluo dal resto, e non rende significativamente più veloce il programma.
Inoltre, hai dimenticato di specificare la condizione di ritorno in questo caso. (Lo vedi subito dall'indentazione.)
La condizione r<=sqrt(a) equivale a r*r<=a, la quale ha il vantaggio di usare solo int.
I valori di ritorno del test su a%r sono scambiati: se a%r==0, allora a è divisibile per r.
Cosa ancora più grave: il "return 0" sta dentro il ciclo for, col risultato che questo viene eseguito una volta sola.
lucas87
22-11-2006, 14:36
piccolo errore, nel if del ciclo for i ritorni vanno invertiti
lucas87
22-11-2006, 14:38
int is_prime(int a){
/*gli viene passato il numero di fibonacci e dice se questo è o non è primo*/
long r;
if ((a==0)||(a==1)){
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 0;
}
else {
return 1;
}
}
}
}
}
cosi va o no? se nn va mi posti quello giusto...please
/*gli viene passato il numero di fibonacci e dice se questo è o non è primo*/
long r;
if ((a==0)||(a==1)){
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 0;
}
else {
return 1;
}
}
}
}
}
cosi va o no? se nn va mi posti quello giusto...please
mdr268
22-11-2006, 16:34
i+=2 invece di i++ nel for...
si scusate... so usare solo il pascal dove mi sembra non sia possibile incrementare di 2 semplicemente come nel C
si scusate... so usare solo il pascal dove mi sembra non sia possibile incrementare di 2 semplicemente come nel C
cionci
22-11-2006, 16:35
In pascal in tal caso mi sembra che si debba usare un ciclo diverso dal for...
andrea
22-11-2006, 17:04
Leggendo questa discussione mi e' venuto in mente una vecchia discussione, proprio sui numeri primi e crivello di eratostene, con diversi codici; pero' cercando con il search non la ho trovata. Non e' che qualcuno se la ricorda e magari ha il link?(se esiste ancora).
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.