01: #include<stdio.h>
02: #include<stdlib.h>
03: #include<math.h>
04: 
05: int ferm(unsigned int);
06: 
07: int main(int argc, char **argv){
08: 
09:   int npn = 0;               // per memorizzare quanti numeri man mano genero
10:   unsigned int n, *arr=NULL; // arr mi permette di gestire l'array dinamico. Inizialmente vuoto e quindi pongo a NULL
11: 
12:   // chiedo ad utente valore massimo intervallo
13:   do
14:   {
15:     printf("Inserisci il valore massimo > 1 per cui calcolare i numeri primi: ");
16:     scanf("%u", &n);
17:   }
18:   while(n <= 1);
19: 
20:   printf("Calcolo i numeri primi da 1 a %d\n", n);
21:   // ciclo tra 1 e n
22:   for(int i = 0; i < n; ++i)
23:   {
24:     printf("%d\r", i); // dato che per valori alti la scomposizione puo' essere lenta stampo il numero in esame e con \r riporto il cursore ad inizio riga
25:     if(ferm(i) == 2) // 2 significa che il numero e' divisibile solo da 1 e se stesso, ovvero e' un numero primo
26:     {
27:       ++npn; // incremento contatore dei numeri primi
28:       arr = realloc(arr, npn*sizeof(unsigned int)); // allargo array di modo che possa contenere npn elementi. Quindi di fatto aggiungo un solo elemento in piu'
29:       arr[npn-1] = i; // memorizzo ultimo numero primo trovato come ultimo elemento
30:     }
31:     printf("               \r"); // stampo un po' di spazi per cancellare quanto stampato prima dell'if() e ritorno comunque ad inizio riga
32:   }
33: 
34:   getchar(); // rimuove lo '\n' rimasto da lettura precedente
35:   printf("Premi invio per vedere i %d numeri che ho trovato", npn);
36:   getchar();
37: 
38:   // scorro array
39:   for(int i = 0; i < npn; ++i)
40:     printf("%4d: %u\n", i+1, arr[i]);
41: 
42:   return 0;
43: }
44: 
45: 
46: int ferm(unsigned int n)
47: {
48:   if(!n) return 0; // 4.a
49: 
50:   if(n == 1){ //4.b
51:    return 1;
52:   } 
53: 
54:   if(!(n%2)){ //4.c
55:    return 1 + ferm(n/2); 
56:   }
57: 
58:   // da qui in poi 4.d
59: 
60:   // unsigned long long per evitare overflow
61:   unsigned long long a  = ceil(sqrt(n)); // ci finisce l'intero che approssima PER ECCESSO la radice quadrata di n
62:   unsigned long long b2 = a*a - n;
63:   unsigned long long b  = sqrt(b2);      // solo parte intera della radicequadrata di b2
64:   while(b*b != b2) // se la parte intera della radice quadrata moltiplicata per se stessa ci restituisce b2 allora b2 era un quadrato 
65:   {
66:     ++a;
67:     b2 = a*a - n;
68:     b  = sqrt(b2);
69:   }
70: 
71:   if((a+b) == n){
72:    return 2; 
73:   }
74:   return 1+ferm(a+b); 
75: }
76: 
77: