Newsgroup: it.comp.lang.c
Titolo: [Il più niubbo dei quesiti] Numeri primi

Ciau,
mi sto avvicinando al c dopo aver usato per un bel po' il turbo pascal.
Avevo intenzione di trasporre questo semplice programmino in TP...
***
uses crt;
var i,j:longint;
var divm,primo:boolean;
begin
 clrscr;
 for i:=300000001 to 300000049 do
  begin
  divm:=false;
   for j:=1 to i div 2 do
    begin
     if i mod j = 0 then
      if (i div j <> 1) and (i div j <> i) then
       divm:=true;
    end;
   if not divm then writeln (i);
  end;
  writeln('--Fine--');
 readln
end.
***
... in C. Ho provato con questo:
***
#include <stdio.h>
main()
{
 int i, j;
 int divm, primo, min, max;
 divm = 0;
 printf("Trova i numeri primi da: ");
 scanf("%d",&min);
 printf("a: ");
 scanf("%d",&max);
 for (i=min; i<=max; i++) {
  divm = 0;
   for (j=1; j<=(i/2); j++) {
    int a = i % j;
    if (a==0) {
     if (i/j != 1 && i/j != i) {
      divm = 1;
    }}
   if (divm == 0) {
    printf("%d",i);
   }
   }
 }
}
***
... ma non funziona. Qualche suggerimento :)?
-- 
L'           è invisibile agli occhi
http://scriverefantascienza.blogspot.com/
 

 }
1) manca il "\n" per andare a capo nella stampa, o almeno
uno spazio e quindi stampa tutto attaccato.
2) hai messo il test su dimv dentro il ciclo piu' interno.
Devi spostare una parentesi graffa:
 >     }}}
 >    if (divm == 0) {
 >     printf("%d\n",i);
 >    }
 >  }
 > }
Se poi mi permetti, il programma ha anche dei problemi
di efficenza. (Queste non sono critiche a te, ma consigli
per migliorare).
Infatti vai avanti a dividere fino a i/2 mentre
dovresti andare avanti a dividere solo fino alla radice
di i. Se i e' grande, per esempio 10 milioni, questo
vuol dire fare 5 milioni di cicli quando ne basterebbero 10mila.
Inoltre non ha senso dividere per tutti i numeri pari
superiori a 2 visto che non possono essere primi.
Non ha neanche senso il controllo i/j!=i e i/j=i.
Perche' sia i/j=1 bisogna che i=j, ma j arriva solo fino a i div 2.
Perche' sia i/j=i bisogna che sia j=1, ma questo potresti
evitarlo semplicemente facendo iniziare il ciclo invece che
dall'inutile j=1 almeno da j=2.
Riassumendo, il programma, senza arrivare a complicarlo
troppo, potrebbe essere riscritto in questo modo:
#include <stdio.h>
int main()
{
  int min, max, n, d, primo;
  printf("Trova i numeri primi da: ");
  scanf("%d",&min);
  printf("a: ");
  scanf("%d",&max);
/* queste righe servono per evitare di stampare
  1, che non e' primo e invece stampare 2 se
  e' entro i limiti, visto che e' l'unico primo pari */
  if (min<=1) min=2;
  if (min==2 && max>=2) printf("2 ");
  for (n=min; n<=max; n++)
  {
/* se n e' pari e >2 non e' primo */
   if ((n%2)==0) continue;
   primo=1;
/* prova a dividere per i numeri dispari fino
    alla radice quadrata di n */
   for (d=3; d*d<=n; d+=2)
      if ((n%d)==0)
      {
       /* trovato un divisore, esco */
        primo=0; break;
      }
   if (primo)  printf("%d ",n);
  }
printf("\n");
return 0;
}
ciao,
v.

 per migliorare).
[...]
Grazie mille! Farň tesoro dei tuoi consigli.
Solo un'ultima cosa. Come fare per far sě che il programma non si chiuda e 
mi permetta di leggere il risultato? L'equivalente del readln in TP, 
insomma. Ho provato con un scanf di una variabile a caso, ma non funziona 
(e poi non č certo un modo elegante).
thanx :)!
-- 
L'           č invisibile agli occhi
http://scriverefantascienza.blogspot.com/
 

 Solo un'ultima c
Anzi, no, ancora un'altra :). Perché basta arrivare alla radice quadrata 
:)?


 thanx :)!
Non lo so perche' quando facevo programmi sotto DOS io tenevo
comunque aperta una finestra DOS dalla quale lanciavo i programmi.
Pero' mi sembra che la gente usi qualcosa tipo getc o getchar o
qualcosa di simile (una di quelle che legge un carattere e aspetta)
ciao,
v.

 :)?
http://it.wikipedia.org/wiki/Fattorizzazione
e
http://it.wikipedia.org/wiki/Crivello_di_Eratostene
-- 
Firma in costruzione

 :)?
l
perche' se un numero non e' primo deve avere almeno un
fattore (primo o composto, non importa) minore o
uguale alla radice quadrata.
Dimostriamolo per assurdo, assumendo che non sia vero.
Se non fosse vero avremmo ad esempio un numero composto
N uguale al prodotto di due fattori entrambi maggiori strettamente
di radice di N, diciamo N=x * y con x,y>sqrt(N).
Ma se x>sqrt(N) e y>sqrt(N), moltiplicando membro a membro
le disuguaglianze otteniamo
x*y > sqrt(N)*sqrt(N) = N
cioe' abbiamo dimostrato che x*y>N mentre eravamo partiti
ipotizzando x*y=N. Siccome siamo arrivati ad un assurdo
significa che l'ipotesi di partenza e' falsa e quindi
ogni numero composto ha almeno un fattore minore o uguale
alla sua radice.
ciao,
v.

 Dimostriamolo per assurdo, assumendo che non sia vero.
[...]
Giusto... ci sarei dovuto arrivare da solo :).
ciau!
