Home > Listati di programmi C > Ricerca di numeri primi

RICERCA DI NUMERI PRIMI

Il programma primi.c cerca i numeri primi inferiori o uguali al numero passato in input dall'utente (max_ricerca); ogni numero primo trovato viene inserito in una lista concatenata doppia, formata da struct nodo; il 2 e il 3 vengono messi in lista all'inizio dell'elaborazione; la ricerca parte col 5 e prosegue con tutti i numeri dispari successivi, fermandosi quando arriva al valore massimo indicato dall'utente.

Dato un numero dispari, il programma verifica se e' presente nella lista dei primi un suo divisore; se il divisore non viene trovato, significa che il numero e' primo e anche esso viene inserito nella lista.

I primi trovati possono essere salvati in un file di interi, con la funzione lista_file().

Quando i primi vengono salvati su file, al primo posto viene memorizzato (come metadato) il valore massimo di cui e' stata verificata la primalita' (max_ricerca); questo facilita alcune operazioni svolte dagli altri programmi, che devono sapere fino a quale valore e' stata fatta la ricerca dei primi.

Ho previsto un limite "artificiale" al valore massimo di max_ricerca, assegnandogli 1.000.000.000, per evitare elaborazioni troppo pesanti e intasamenti della memoria heap. I primi compresi fino a 1.000.000.000 sono 50.847.534.

I nodi della lista contengono i numeri primi e i gap associati; per gap associato al numero primo P intendo il valore che sommato a P fa ottenere il primo successivo a P.

I gap non vengono salvati in file appositi; l'importante e' salvare i primi, i gap vengono ricalcolati quando si copiano i primi da file a lista, con la funzione file_lista().

I dati vengono visualizzati in questo modo:

IDPrimoGap
121
232
352
474
5112
6134
7172
819il gap non c'e', perche' non si conosce ancora il primo successivo

A parte il primo gap (1), tutti i gap possono essere ripartiti in 3 insiemi:

2, 8, 14, 20, ...., cioe' (6N - 4);

4, 10, 16, 22, ...., cioe' (6N - 2);

6, 12, 18, 24, ...., cioe' (6N);

con N = 1, 2, 3, 4, ....

I miei programmi consentono di visualizzare l'insieme di appartenenza di ogni gap.

Calcolano anche la radice numerica dei primi, cioe' la somma delle cifre che li compongono, iterata fino a ottenere una sola cifra.

Ho verificato che i primi con gap dell'insieme (6N - 4) hanno radice numerica 2, 5, 8 (con l'eccezione del primo 3);

I primi con gap dell'insieme (6N - 2) hanno radice numerica 1, 4, 7;

I primi con gap dell'insieme (6N) hanno radice numerica 1, 2, 4, 5, 7, 8.

Con le funzioni del gruppo copia_..., data una lista di primi, e' possibile estrarre e mettere in una seconda lista solo i primi che rispondono a certe caratteristiche.

copia_intervallo() estrae i primi appartenenti a un certo intervallo;

copia_gap_dato() estrae i primi associati a un dato gap;

copia_insieme_gap() estrae i primi con gap appartenente a un dato insieme;

copia_primo_gap() estrae i primi con la prima occorrenza di ogni gap;

copia_stesso_gap() estrae i primi consecutivi con lo stesso gap;

copia_fatt_gap() estrae i primi con gap contenente un dato fattore primo.

copia_ult_cifra() estrae i primi che terminano con una data cifra;

copia_rad_num() estrae i primi con una data radice numerica;

Sicuramente ci si puo' sbizzarrire a crearne altre analoghe.

Con riferimento alle liste create con le suddette funzioni, ho pensato che si potrebbero fare scoperte interessanti esaminando anche il gap che sommato a un primo fa ottenere il primo successivo (non nella lista di tutti i primi, ma nella lista dei primi selezionati).

Esempio, lista di primi con radice numerica 7:

ID Primo Gap RN primo Gap 2
474736
14434718
18616718
22794718
25974754
361516772
482234718
5324110736
592774736
653134718
673316718
703494718

Esaminiamo la prima riga, dedicata al quarto numero primo, che e' 7; il campo gap=4 indica che sommando (7 + 4) si ottiene il primo successivo nella lista di tutti i primi (11); 11 non e' presente in questa lista, perche' la sua radice numerica non e' 7; gap_2=36 indica invece che sommando (7 + 36) si ottiene il primo successivo in questa lista, cioe' 43; quest'ultimo e' il 14mo nella lista di tutti i primi, ma secondo nella lista dei primi con rad. num. 7.

Ho previsto anche un secondo tipo di lista, formata da struct nodo_freq. Viene usata per la scomposizione in fattori primi e per visualizzare i gap di una lista in ordine decrescente di frequenza.


Per compilare un programma (con gcc): gcc -o primi primi.c primi_lib.c

File primi_lib.h

File primi_lib.c

Ricerca di numeri primi ed eventuale salvataggio su file

Leggere un file di primi creato con primi.c e copiare i numeri in lista

Estrarre informazioni varie da lista di numeri primi

Salvare in file HTML numeri primi e altri dati

Esempi di tabelle generate con crea_html.c:

Numeri primi fino a 1.000

Numeri primi fino a 1.000.000 (5,7 MB)

Numeri primi compresi fra 999.000.000 e 1.000.000.000 (3,9 MB)

Numeri primi fino a 100.000 con gap 10

Numeri primi fino a 1.000 con gap dell'insieme (6N - 4), cioe' 2, 8, 14, 20, ...

Numeri primi fino a 1.000 con gap dell'insieme (6N - 2), cioe' 4, 10, 16, 22, ...

Numeri primi fino a 1.000 con gap dell'insieme (6N), cioe' 6, 12, 18, 24, ...

Prima occorrenza di ogni gap dei numeri primi fino a 1.000.000.000

Numeri primi consecutivi con lo stesso gap fino a 1.000.000

Numeri primi fino a 100.000 con gap contenente il fattore primo 5

Numeri primi fino a 10.000 con ultima cifra 1

Numeri primi fino a 10.000 con radice numerica 7


Home


www.corradodamiano.it a cura di Corrado Damiano

posta@corradodamiano.it