Newsgroup: it.comp.lang.c++
Titolo: Fattori primi

Salve, non esiste una funzione per fare la scomposizione in fattori primi di
un qualsiasi numero intero.
Ciao
--
Timothy Redaellli

 primi di un qualsiasi numero intero.
e' proprio vero, non esiste

 wrote in message
news:a3p4dd$19pcma$1...@ID-87006.news.dfncis.de...


Timothy wrote:

Non c'e' una funzione gia' fatta in C++, comunque e' un problema abbastanza 
facile da risolvere; il metodo migliore e' usare l'algoritmo di Euclide. E' 
descritto e analizzato in profondita' in "The Art of Computer Programming", 
volume 1, di Donald E. Knuth. Se non ce l'hai (e tutti programmatori 
dovrebbero averlo) sono sicuro che troverai l'algoritmo con google.
Aaron

 un qualsiasi numero intero.
Ho fatto, però ho un problema:
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<unsigned long>scomp(const unsigned long n);
int main()
{
      vector<unsigned long>A=scomp(4294967295L);
      for(unsigned long I=0;I<A.size();I++)
            cout<<A[I]<<endl;
      system("PAUSE");
      return 0;
}
vector<unsigned long>scomp(const unsigned long n)
{
      vector<unsigned long>fattori;
      unsigned long tmp=n;
//Temporanea=n
next:
      for(register unsigned long I=2;I<=tmp;I++) {                //For I da
tmp a 2
            if(tmp%I==0)
 //Se il resto fra il numero e I=0
                  fattori.push_back(I);
//Aggiunge l'elemento
                  tmp/=I;
//tmp=tmp/I
                  goto next;
//Ricomincia il for
            }
      }
      sort(fattori.begin(),fattori.end());
//Per sicurezza :-)
      return fattori;
}
Ho un problema, dopo vorrrei scriverli in forma classica del tipo
(20=2^2*5)...
Ho provato di tutto, ma niente da fare....
Suggerimenti????
Grazie
--
Timothy Redaelli

 Suggerimenti????
a bruciapelo mi viene in mente una map<elemento, num_volte_trovato>
al posto del vector. pero' ogni volta che inserisci devi controllare che non
ci sia gia'
--
Ciao by Allanon

 wrote in message
news:a3pg5u$1a84g4$1...@ID-87006.news.dfncis.de...


 Timothy Redaelli
Ciao,
guarda, questo che copio qui sotto e' qualcosa che ho fatto parecchio tempo
fa. Funziona, ma non l'ho nemmeno rivisto ed e' di sicuro criticabilissimo.
Vedi se ti può dare uno spunto per farlo meglio.
Ed eventualmente se lo realizzi bene me lo rimandi?
Ciao,
Myszka
// ------
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>
int main(int argc, char* argv[])
{
  //system("cls");
  char         x = '0';
  char         line[11];
  unsigned int numero = 0;
  unsigned int prova  = 1;
  unsigned int valore = numero;
  unsigned int conta  = 0;
  div_t        result;
  unsigned int array[100];
  while (1) {
    printf("\n\n\n\t\tDimmi un numero (max 9 cifre):   ");
    gets(line);
    line[10]='\0';
    //if ((line[0] > 4)) {
    //  printf("\n\n\t\tBeh, quel numero e' troppo grande...\n\t\tPuoi
provare a scomporlo con carta e penna.\n\n\t\t",numero);
    //  break;
    //}
    // due controllini sul numero immesso
    numero = atoi(line);
    if ((numero == 0) || (numero < 0)) {
      printf("\n\t\tBeh, ovviamente %d non si puo'
scomporre...\n\n\t\t",numero);
      break;
    }
    printf( "\t\tScompongo %s in fattori...\n\n", line );
    prova  = 1;
    valore = numero;
    conta  = 0;
    for (int i=0; i<100; i++) { array[i]=0; } // inizializzo l'array
    while (prova<=sqrt(valore)) {
      prova++;
      //printf( "Il numero e' %d, ed il divisore e' %d... ", numero,
prova );
      result = div(numero, prova);
      //printf( "Il quoziente e' %d, ed il resto e' %d\n\n", result.quot,
result.rem );
      if (result.rem == 0) {
        //printf("\t\tIl tuo numero e' divisibile per %d, \n", prova);
        array[prova] = array[prova] + 1;
        numero = numero / prova;
        prova = 1;
        conta++;
      }
    }
    if (conta == 0) {
      printf("\t\t%d e' un numero primo!\n",valore);
      printf("\n\t\tFine.\n\t\t");
    }
    if (conta != 0) {
      printf("\t\tIl numero %d si scompone cosi':\n\t\t",valore);
      for ( i=0; i<100; i++) { // scorro l'elenco dei divisori
        if (array[i] != 0) { // ne ho trovato uno
          if (array[i] > 1) { // se l'esponente non e' uno...
            printf("%d^%d   ",i,array[i]); // stampa anche la potenza
            conta = conta - array[i] + 1;
          }
          else {
            printf("%d   ",i); // altrimenti stampa solo il divisore
          }
        }
      }
      if (numero != 1) { // se non sono arrivato a 1, vuol dire che mi sono
fermato
        printf("%d   ",numero); // e il numero rimasto e' primo
        conta = conta + 1;
      }
      printf("\n\n\t\tIl numero %d e' stato scomposto in %d
divisori\n",valore, conta);
      printf("\n\t\tFine.\n\t\t");
      //printf("\t\te per %d.\n",numero);
    }
    //if (numero == 1){
    //  printf("\t\tIl tuo numero %d e' stato scomposto in %d
divisori\n",valore, conta);
    //  printf("\n\t\tFine.\n\t\t");
    //}
  printf("Premere ESC per uscire.\n\t\t");
  x = getch();
  if (x == 27) { exit(1); }
  } // end while
  return 0;
}