Jump to content

É possivel decompor números?


SitoMan
 Share

Recommended Posts

Olá pessoal.

Antes de mais peço desculpa pelo estúpido título que dei ao post, mas o que eu quero saber se é possível fazer... não sei o nome!  ?

Ora bem.. Antes de mais só quero saber se é possível fazer, até porque eu acho que não, e também não preciso que seja em C, mas não sabia onde era a zona de "qualquer linguagem".  :wallbash:

Vamos à teoria.. O que eu queria saber se era possivel fazer era qualquer coisa deste género:

Lembram-se de nas aulas de matemática "dividirmos" os números por 2, sempre que desse por 2, depois por 3, depois por 4, até ficarmos com 1??? Pois, é isso mesmo que quero.

Para ser mais preciso... Davam-nos o número 100. Nós dividíamos sempre pelo mais curto que dava número inteiro:

2 = 50

2 = 25

5 = 5

5 = 1

Ou seja.. 2*2*5*5 tem de ser obrigatoriamente igual a 100.

Penso que perceberam o que quero. Não tenho a certeza se o nome é "desfragmentar o número" ou qualquer coisa parecida, mas não me ocorre agora o nome com 100% certezas.

Fico à espera de alguma resposta! Obrigadão!  🙂

EDIT: Já me consegui lembrar do nome, e alterei o título. O nome é "Decompor números".

Link to comment
Share on other sites

Eu conheço como factorização em números primos. O algoritmo mais simples será algo assim:

- começando com factor = 2,

- enquanto o valor a factorizar for maior que 1:

  - se o resto da divisão por factor for zero, dividir e acrescentar factor à lista de factores;

  - senão, passar ao próximo número primo (que será 3, depois 5, depois 7...), e repetir.

Desaparecido.

Link to comment
Share on other sites

Olá pessoal.

Antes de mais peço desculpa pelo estúpido título que dei ao post, mas o que eu quero saber se é possível fazer... não sei o nome!  ?

Ora bem.. Antes de mais só quero saber se é possível fazer, até porque eu acho que não, e também não preciso que seja em C, mas não sabia onde era a zona de "qualquer linguagem".  :wallbash:

Vamos à teoria.. O que eu queria saber se era possivel fazer era qualquer coisa deste género:

Lembram-se de nas aulas de matemática "dividirmos" os números por 2, sempre que desse por 2, depois por 3, depois por 4, até ficarmos com 1??? Pois, é isso mesmo que quero.

Para ser mais preciso... Davam-nos o número 100. Nós dividíamos sempre pelo mais curto que dava número inteiro:

2 = 50

2 = 25

5 = 5

5 = 1

Ou seja.. 2*2*5*5 tem de ser obrigatoriamente igual a 100.

Penso que perceberam o que quero. Não tenho a certeza se o nome é "desfragmentar o número" ou qualquer coisa parecida, mas não me ocorre agora o nome com 100% certezas.

Fico à espera de alguma resposta! Obrigadão!  🙂

EDIT: Já me consegui lembrar do nome, e alterei o título. O nome é "Decompor números".

não estou a perceber a pergunta

Learning

  • VB.Net
  • HTML
  • C/C++

Link to comment
Share on other sites

não estou a perceber a pergunta

Sabes o que é Decomposição de Números em Factores Primos?

É o que o SitoMan pretende fazer.

Lê os posts anteriores................ :wallbash:

Eu conheço como factorização em números primos. O algoritmo mais simples será algo assim:

- começando com factor = 2,

- enquanto o valor a factorizar for maior que 1:

  - se o resto da divisão por factor for zero, dividir e acrescentar factor à lista de factores;

  - senão, passar ao próximo número primo (que será 3, depois 5, depois 7...), e repetir.

O que procuras chama-se mesmo factorizar um número e o método mais simples é mesmo essa "trial division".

Para perceberes melhor, se estiveres confortável com inglês, espreita por exemplo: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers (onde te são dadas mais alternativas algorítmicas)

Knowledge is free!

Link to comment
Share on other sites

Tens aqui um exemplo em c++. Nao testei:

#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
using namespace std;
int primos[10000];
void primar(int mbm) {
    int nactual=0;
    bool numeros[100000];
    for (int x=0;x<=100000;x++) {
numeros[x]=true;
    }
    for (int x=2;x<=mbm;++x) {
if (numeros[x]==true) {
    for (int y=x;y<mbm;++y) {
	if (numeros[y]==true) {
            if(y%x==0) {
	        numeros[y]=false;
            }
	}
    }
	    primos[nactual]=x;
    nactual++;
    cout << nactual << "\n";
}
    }
}
std::string i2string(int i) {
std::ostringstream buffer;
buffer << i;
return buffer.str();
}
string decompor(int n) {
    int mn=n;
    int z,v=0;
    int RESPOSTA[20];
    int ru=0; // numero de repostas utilizadas
    string resposta="";
    bool naofeito=true;
    for (;naofeito;) {
for(int w=2; {
    if (mn%w==0) {
	RESPOSTA[ru]=w;
	ru++;
	break;
    }
    v++;
    w=primos[v];
    if (w>mn) {
	naofeito=false;
	break;
    }
}
    }
// utiliza aqui um sort qualquer para pores os numeros por ordem numerica
    for (int d=0;d<(ru-1);d++) {
resposta = resposta + i2string(RESPOSTA[d]) +" * ";
    }
    resposta = resposta + i2string(RESPOSTA[(ru-1)]) +" * ";
    return resposta;
}

int main() {
int N;
string decomposicao;

cin >> N;
primar(N);
decomposicao=decompor(N);
cout << decomposicao << "\n";
return 0;
}

Alguem me sabe dizer se o crivo de eratostenes esta bem feito?

<Signature goes here>

Link to comment
Share on other sites

O crivo parece estar funcional ... no entanto, tens uma parte que está muito mais complexa e ineficiente do que é necessário:

            for (int y=x;y<mbm;++y) {
                if (numeros[y]==true) {
                    if(y%x==0) {
                        numeros[y]=false;
                    }
                }
            }

pode passar a:

for (int y=2;x*y<mbm;++y) {
  numeros[y*x] = false;
}
Link to comment
Share on other sites

Nao nao pode. O que eu pretendo com essa expressão é por false em todos os numeros que nao sao primos. E nao meter verdadeiro em x*y.

Para ficar mais claro:

x é o numero primo que estou a multiplicar e a remover os multiplos da lista de numeros primos.

y e o numero a ser analisado no momento.

Tendo assim, matematicamente:

X mod Y = 0 é diferente de x * y < k

O teu codigo nao verifica se o numero ja foi "riscado" ou não, tornando-o assim mais "gastador" de processos.

Se y=2, entao nao sera analisado nenhum numero impar. ja que apenas sao feitas contas de vezes.

<Signature goes here>

Link to comment
Share on other sites

oops, enganei-me xD queria pôr false.

E o código que fiz, estava incompleto ... indiquei o pedaço de código que devias substituir, ficando o resto igual ... mas já que queres o crivo completo, ficaria assim:

int primos[10000];
void primar(int mbm) {
    int nactual=0;
    bool numeros[100000];
    for (int x=0;x<=100000;x++) {
        numeros[x]=true;
    }
    for (int x=2;x<=mbm;++x) {
        if (numeros[x]==true) {
            for (int y=2;y*x<mbm;++y) {
                numeros[y*x]=false;
            }
            primos[nactual]=x;
            nactual++;
            cout << nactual << "\n";
        }
    }
}

PS: Editei a minha mensagem anterior para corrigir o erro.

Link to comment
Share on other sites

Assim?:

void primar(int mbm) {
    int nactual=0;
    bool numeros[100000];
    for (int x=0;x<=100000;x++) {
    numeros[x]=true;
    }
    for (int x=2;x<=mbm;++x) {
    if (numeros[x]==true) {
            for (int y=x;y<mbm;y+x) {
                if (numeros[y]==true) {
                    if(y%x==0) {
                        numeros[y]=false;
                    }
                }
            }
         primos[nactual]=x;
        nactual++;
        cout << nactual << "\n";
    }
    }
}

<Signature goes here>

Link to comment
Share on other sites

Assim?:

void primar(int mbm) {
    int nactual=0;
    bool numeros[100000];
    for (int x=0;x<=100000;x++) {
    numeros[x]=true;
    }
    for (int x=2;x<=mbm;++x) {
    if (numeros[x]==true) {
            for (int y=x;y<mbm;y+x) {
                if (numeros[y]==true) {
                    if(y%x==0) {
                        numeros[y]=false;
                    }
                }
            }
         primos[nactual]=x;
        nactual++;
        cout << nactual << "\n";
    }
    }
}

Ainda não percebeste bem ...

O que o Warrior queria dizer era:

int primos[10000];
void primar(int mbm) {
    int nactual=0;
    bool numeros[100000];
    for (int x=0;x<=100000;x++) {
        numeros[x]=true;
    }
    for (int x=2;x<=mbm;++x) {
        if (numeros[x]==true) {
            for (int y=2*x;y<mbm;y+=x) {
                numeros[y]=false;
            }
            primos[nactual]=x;
            nactual++;
            cout << nactual << "\n";
        }
    }
}

(PS: obrigado pela dica, nunca me lembrei disso xD)

Não precisas de verificar se y%x == 0, visto que, ao começares por 2x, e avançares de x em x, isso é sempre verdadeiro!

PS: No teu código, não há indentação do y, visto que y+x não faz nada.

Também não precisas de verificar se numeros[y]==true, visto que é mais "caro" em termos de performance fazer a comparação+atribuição do que só a atribuição!

Link to comment
Share on other sites

Nao percebi se o "execicio" era para mim ou para o cynary. se nao fosse para mim então nao olhes cynary

(...)

Porque os numeros a processar so são multiplos de x se forem maiores que x.

O exercício provavelmente era para todos os que percebessem a pergunta xD

E essa não é a resposta 🙂 , visto que 2*x é maior que x também.

Eu percebi a pergunta, e até já tinha pensado nisso, não tinha era chegado a essa solução simples de começar em x*x.

O que acontece é o seguinte: Como já riscámos todos os múltiplos dos números primos até x, e todos os números até x podem ser divididos por esses primos, os múltiplos 2*x, 3*x, ... até x*x (exclusive) já foram riscados.

Obrigado pela nova dica B)

Uma pergunta: SitoMan, já percebeste como podes fazer para decompor números de uma forma eficiente?

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.