Decomposição em fatores primos

Publicado por Enzo de Brito Ferber 28/03/2009

[ Hits: 14.580 ]

Homepage: http://www.maximasonorizacao.com.br

Download primes.c




Sim, eu tenho outro script desse aqui no VOL, mas esse está bem melhor (mais compacto e rapido).

Outra coisa, o código está em inglês como sempre, pois este site não é o unico que publico (e o ingles é a linguagem internacional da informática).

Então, happy coding!

  



Esconder código-fonte

// primes.c

/* Enzo Ferber : <enzo@veloxmail.com.br>
 * 
 * Decompose into Prime Factors a given number
 *
 * march 27 2009
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define START 2

// used by the main() function to print the factors
int control;

/* decom ( num )
 *
 * @ num: number to decompose
 * 
 * @ Return: return an int* containing all the prime factors
 */
int *decom ( int num )
{
    // ...
    register int i;
    int *primes = (int *) malloc ( sizeof (int) );
    
    // Houston, we have a problem!
    if ( !primes ) exit (0);
    
    // set control variable
    control = 1;
    
    // START represents the first prime number, 2
    for ( i = START; i <= num || num != 1 ; i++ )
    {
        // ensures just an exact division
        while ( (num % i) == 0)
        {
            // I WANT MORE MEMORY, BITCH!!!
            primes = (int *) realloc ( primes, control * sizeof (int));
            
            // Houston, we have a problem!
            if ( !primes) exit (0);
            
            // put the current prime factor into the list
            primes[control - 1] = i;
            control++;
            
            // set new number to be divided next
            num = num / i;
        }
    }
    
    // return the prime list
    return primes;
}

int main ( int argc, char **argv )
{
    // check for the correct argument
    if ( argc != 2 )
    {
        // HowTo use a very complex program...
        printf ( "Usage: %s <number>\n", argv[0] );
        return 0;
    }
    
    // begin the program if the arguments are correct
    register int i;
    
    // call the function to decompose into prime factors
    int *primes = decom ( atoi(argv[1]) );
    
    // print prime list
    for ( i = 0; i < control - 1; i++ )
        printf ( "%3d: %d\n", i + 1, primes[i] );
        
    // free the memory
    free ( primes );
    
    
    return 0;
}


Scripts recomendados

Exceções em C através de try-throw-catch

Balanceamento de parênteses utilizando Pilha

Matrizes esparsas, produto por escalar e produto por um vetor

Aterm multicolor v0.02

Gerando uma "number list" de 6 digitos


  

Comentários
[1] Comentário enviado por igorlg em 28/03/2009 - 17:19h

cara, muito bom teu script, mas tenho um complemento se performance pra fazer...

na linha for ( i = START; i <= num || num != 1 ; i++ ), tu nao precisa testar o i até num, mas sim até a raiz quadrada de num, já que o maior primo que pode dividir num é a raiz quadrada dele mesmo...

ou, no caso, a raiz de índice START, se START != 2...

mas fora isso ta legal!

atualiza teu script...
Abraços

[2] Comentário enviado por EnzoFerber em 28/03/2009 - 18:37h

bom, pode ate ser,
mais uma rotina para calcular a raiz quadrada de um numero pode ser inclusive mais demorada do que percorrer até num.

Mais gostei de sua ideia, vou refazer o codigo e ver como fica,

obrigado por colaborar,
Slackware_10
[]'s


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts