[C] funzione C per numeri primi

[rocco.g]

Ciao a tutti,
ho trovato un esercizio in C che diceva di scrivere una funzione in C che preso un input un intero n restituisse come output i primi n numeri primi in un puntatore a vettore...
ho provato a farlo, ma non mi viene in mente l'algoritmo per il calcolo dei numeri primi...

[Webmaster76]

Un numero è detto primo quando è divisibile solo per se stesso e per 1; due numeri sono divisibili quando il resto intero della loro divisione è zero ( es. 8 è divisibile per 2 poiché 8 : 2 = 4 con resto 0).

Fai un ciclo e valuti i resti...

[LeleFT]

Algoritmo per il test di primalità:

Si controllano tutti i numeri a partire da 2 fino all'intero della radice del numero.

Se uno di questi numeri divide x allora non è primo, in caso contrario è primo.

Esempio:

int primo(int x) {
   int tmp = 0;
   int i = (int) sqrt(x);
   int t = 2;
   int trovato = -1;
   if (x < 2) tmp = 1; // 1 non sarebbe primo, ma non discutiamo
   while (t <= i && trovato) {
      trovato = (x % t);
      t++;
   }
   if (trovato) tmp = -1;
   return tmp;
}

Questo dovrebbe essere sufficiente.


Ciao.

[Webmaster76]

Non mi convince mica quella radice quadrata!!! il 10 per il tuo algoritmo è primo!

[LeleFT]

Riprova... a me dice che 10 non è primo.

Se vuoi ti spiego il meccanismo:
trovato riceve il valore del resto della divisione fra il numero passato come argomento e t (t indica il valore che sono arrivato a testare). Se è 0 il numero è divisibile per t, quindi esce dal while e si accorge che non è primo, altrimenti continua fino alla radice del numero.

Non ha senso testare per valori superiori alla radice del numero, perchè se esiste un valore che lo divide, che sia maggiore della radice, allora ne esiste un'altro minore:

a / b = c + q quindi se q = 0 a = b * c, può capitare che c sia prprio uguale a b (in questo caso a = b ^ 2 e b è la sua radice), ma se sono differenti uno dei due è minore della radice, e lo divide!


Ciao.

[Webmaster76]

Ok, ok...

Ho anche trovato questo che spiega molto bene l'algoritmo (ancora più ottimizzato): http://www.matematicamente.it/numeri...ione_primi.pdf

[LeleFT]

Effettivamente l'algoritmo è estremamente migliorabile, aggiungendo il controllo solo sui dispari.

In via teorica è possibile testare solo sui numeri primi precedenti la radice... ma qui rientriamo nel caso del cane che si morde la coda: come estraiamo tutti i primi minori della radice? Mi serve un algoritmo per testare la primalità... :gren:

In realtà esiste un algoritmo polinomiale, che è stato realizzato pochi anni fa... si chiama AKS (dalle iniziali dei suoi tre inventori), ma non mi ci metto nemmeno a capirlo...


Ciao.

[iguana13]

Mi ridai il link dell'AKS che ho perso?

[JamesD]

Originariamente inviato da LeleFT
... ma qui rientriamo nel caso del cane che si morde la coda: come estraiamo tutti i primi minori della radice? Mi serve un algoritmo per testare la primalità... :gren:
...

Ricorsione

[rocco.g]

grazie per aver risposto...ora l'algoritmo mi è chiaro...
cmq il programma non doveva solo verificare se un numero fosse primo o meno, doveva anke restituire un puntatore ad un vettore contenente i primi n numeri primi...vi faccio un esempio.
Inserendo 5 ad esempio il programma mi dovrebbe restituire una cosa del genere:

1 - 3 - 5 - 11 - 13

cioè i primi 5 numeri primi... domani vedo d ifarmi venire in mente un modo per stamparli, tanto ora l'algoritmo è chiaro, mi basta creare un vettore e riempirlo con i primi n numeri primi...