Newsgroup: it.comp.lang.pascal
Titolo: Scomposizione in fattori e numeri primi

Ciao a tutti,
dovrei fare un programma che dato un numero, lui mi indichi se esso
sia primo o no, in caso il numero non fosse primo, il programma mi
dovrebbe visualizzare la sua scomposizione in fattori es. 12=2*2*3
Come posso fare?
Vincenzo Accardi - (Palermo, ITALY)
 
E-Mail: 
vin...@tiscalinet.it
ICQ UIN: 20344085
 
-------------------------------------------------
Euro Conversion 2000 - Il miglior software per 
convertire le lire in euro e viceversa. Freeware!
http://volftp.tin.it/italiani/accardi/index.htm
-------------------------------------------------

E'una cosa complicata.. 
Innanzitutto per sapere se un numero é primo bisogna fare appositi test
(uno fra questi é il piccolo Teorema di Fermat)..
Non solo, ma tutt'ora non esiste un algoritmo in grado di scomporre
correttamente numero molto grossi in fattori primi..
Il sistema di crittografia RSA, per esempio, si basa sulla difficoltá di
scomporre in fattori primi numeri molto grandi( circa di 200-300 cifre)...
Saluti
	Nathan
--
Posted from 
arp.dada.it
 [194.184.248.7]
via Mailgate.ORG Server - 
http://www.mailgate.org

Come posso fare?
Dovresti specificare l'ordine di grandezza del numero da
scomporre/testare...
per numero piccoli e' una cosa facile, per numeri molto grandi campo
completamente aperto; poi c'e' una fascia intermedia in cui si possono
applicare test di primalita' anche abbastanza sofisticati.
Naturalmente con una ben solida conoscenza di teoria dei numeri (molti
test di primalita' credo si basino su proprieta' di curve ellittiche e
cose simili...)
	fabio

Ciao a tutti,
Ho creato un programma che in base ad un numero immesso lui mi dice se
e' primo oppure composto. Adesso devo creare una routine che mi
scomponga il numero composto in fattori... es: dato il numero 12 lui
mi deve visualizzare (2^2*3). Sapete come posso fare???



Allora... come gia' ha detto Fabio, scordati che il prog.
funzioni per numeri grandi :-)
Comunque sia, per testare se n e' primo, verifichi se
e' divisibile per i numeri compresi tra 2 e trunc(sqrt(n)).
Appena trovi che il numero e' divisibile per un x, compreso
tra 2 ed sqrt(n), poni n = n/x.
 
	n := n / x;
ed ora, ripartendo da x, controlli se il nuovo n e' primo,
ossia controllerai se e' divisibile per un qualsiasi numero
compreso tra x e trunc(sqrt(n)), dove pero' questo n e'
il "nuovo" n :-)
Ciao ciao!
Ema ;-)

Come posso fare?
function primo ( x : word ) : boolean ;
var i, y : word ;
begin
  primo := true ;
  y := round ( sqrt ( x ) ) ;
  for i := 2 to y do
    if ( x mod i ) = 0 then
    begin
      primo := false ;
      exit ;
    end ;
end ;
procedure scomponi ( x : word ) ;
var k : word ;
begin
  if primo ( x ) then write ( x, ' ' )
  else
  begin
    for k := x-1 downto 2 do
      if ( x mod k ) = 0 then
      begin
        scomponi ( k ) ;
        x := x div k ;
      end ;
    if ( x > 1 ) then write ( x, ' ' ) ;
  end ;
end ;
begin
  writeln ;
  scomponi ( 1800 ) ;
end.

Un'altra soluzione puo' essere:
program   scomposizione;
function  fattorizza(n:longint; var i:longint):longint;
var       t:longint;
begin
          i:=2;
          t:=round(sqrt(n));
          while ((n mod i)<>0) and (i<t) do
             inc(i);
          if (n mod i)<>0 then begin
             i:=0;
             fattorizza:=n
          end
          else begin
             write(i,'*');
             fattorizza:=fattorizza( (n div i) , i)
          end
end;
var       n,i:longint;
begin
          writeln;
          readln(n);
          write(n,' = ',fattorizza(n,i));
          writeln
end.
Andrea cosa ne dici.
Secondo te la funzione  FATTORIZZA  puo' essere considerata ricorsiva?
Bo!!!   Penso di no.
Ciao,  Fabio
--
fabi...@rocketmail.com

Bo!!!   Penso di no.
Certo che e' ricorsiva, il fatto stesso che chiami se stessa ne e' la
prova.