1

Tenho o seguinte enunciado do problema:

Um método que recebe um número inteiro como parâmetro e retorna uma lista de inteiros com seus fatores primos decompostos. Como exemplo, se a entrada for o número 36, o método retorna uma lista contendo [2, 2, 3, 3].

  • Chamei o metodo na MAIN: System.out.println(b(36));
  • Resultado esperado: [2,2,3,3].

Consegui implementar o seguinte método:

public static List<Integer> b(int x){
   List<Integer> numeros = new ArrayList<Integer>();
   int aux = x, i = 2, y = 0;

    while (i <= x) {
        if((primo(i) == true) && aux % i == 0){
            aux = x / i;
            numeros.add(y, i);
            y++;
        } else {
            i++;
        }
    }        
    return numeros;
}

Erro:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:3210)
    at java.util.Arrays.copyOf(Arrays.java:3181)
    at java.util.ArrayList.grow(ArrayList.java:261)
    at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235)
    at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227)
    at java.util.ArrayList.add(ArrayList.java:475)
    at desafio6.Desafio6.b(Desafio6.java:54)
    at desafio6.Desafio6.main(Desafio6.java:14)
/Users/alissonfernando/Library/Caches/NetBeans/8.1/executor-snippets/run.xml:53: Java returned: 1
FALHA NA CONSTRUÇÃO (tempo total: 25 segundos)
4
  • E qual sua dúvida?
    – Maniero
    3/09/2017 às 1:26
  • Como eu disse no titulo, não estou familiarizado com esse tipo de erro então me perdi... 3/09/2017 às 1:28
  • 1
    Não tem memória suficiente para lidar com tudo isto, provavelmente porque a lógica está errada e está gerando uma lista enorme.
    – Maniero
    3/09/2017 às 1:30
  • Obrigado amigo, vou tentar debugar novamente... A pergunta fica aberta para novas ideias... 3/09/2017 às 1:31

2 Respostas 2

2

Baseando-se na resposta do Isac, dá para fazer algumas melhorias:

public static List<Integer> fatorar(int x) {
   List<Integer> numeros = new ArrayList<Integer>();
   int aux = x, s = (int) Math.sqrt(x);

   for (int i = 2; i <= s; i++) {
        if (primo(i)) {
            while (aux % i == 0) {
                aux /= i;
                s = (int) Math.sqrt(aux);
                numeros.add(i);
            }
        }
   }

   if (aux != 1 || numeros.isEmpty()) numeros.add(aux);
   return numeros;
}

As melhorias são:

  1. Usar aux /= i.

  2. Evitar verificar mais de uma vez se o mesmo número é primo.

  3. Uma vez que o aux é divido, o limite superior de busca de primos se reduz.

  4. Nenhum número aux tem divisor (que não ele mesmo) maior que a sua raiz quadrada.

  5. Com a otimização da raiz quadrada, se o aux final for primo (ou se o próprio x for primo) ele acaba não sendo adicionado na lista. O if no final faz isso.

Como ele disse, o problema era você ter o aux = x / i, que fazia ele ficar para sempre recalculando o mesmo valor e para sempre preso no laço. Exceto que ele ia adicionando elementos na lista até ela explodir. Além disso, a variável y não é necessária.

Eis o teste:

public static void main(String[] args) {
    System.out.println("36: " + fatorar(36));
    System.out.println("60: " + fatorar(60));
    System.out.println("120: " + fatorar(120));
    System.out.println("144: " + fatorar(144));
    System.out.println("97: " + fatorar(97));
    System.out.println("128: " + fatorar(128));
    System.out.println("15: " + fatorar(15));
    System.out.println("2: " + fatorar(2));
    System.out.println("7: " + fatorar(7));
    System.out.println("1: " + fatorar(1));
    System.out.println("0: " + fatorar(0));
}

Eis a saída:

36: [2, 2, 3, 3]
60: [2, 2, 3, 5]
120: [2, 2, 2, 3, 5]
144: [2, 2, 2, 2, 3, 3]
97: [97]
128: [2, 2, 2, 2, 2, 2, 2]
15: [3, 5]
2: [2]
7: [7]
1: [1]
0: [0]

veja aqui funcionando no ideone.

2

A divisão não está a ser feita pelos valores certos, aqui:

aux = x / i;

Que divide sempre pelo valor original e não pelo ultimo. Dividindo pelo original o aux fica sempre em 18 (36/2) e nunca muda, gerando uma lista infinita de valores iguais, que acaba no erro de memória apresentando.

Devia em vez disso ser:

aux = aux / i;

Os números também já são colocados por ordem fazendo com que o y não seja necessário.

Então o método todo poderia ficar assim:

public static List<Integer> b(int x){
   List<Integer> numeros = new ArrayList<Integer>();
   int aux = x, i = 2; //sem y

   while (i <= x) {
        if(primo(i) && aux % i == 0){
            aux = aux / i; //divisão correta agora aqui, ou aux/=i para ficar curto
            numeros.add(i); //adição normal à lista
        } else {
            i++;
        }
   }

   return numeros;
}

Exemplo no Ideone para confirmar

5
  • Dá para melhorar isso. (1) eliminar o == true. (2) Dá para usar i <= s no while, onde s é int s = (int) Math.sqrt(x);. (3) ao invés de aux = aux / i;, dá para usar aux /= i;. (4) Acho que o i = 2; é desnecessário e apenas deixa as coisas mais lentas. 3/09/2017 às 2:00
  • @VictorStafusa Sim concordo, essas melhorias sintáticas ajudam de facto. Quanto ao começar em 2 de novo, pelo que estive aqui a rever na fatorização parece-me que é impossível que o factor seguinte seja inferior ao ultimo tornando de facto desnecessário esse passo.
    – Isac
    3/09/2017 às 2:08
  • @VictorStafusa Essa sugestão de condição do while é interessante. Chegando a um fator que é a raiz quadrada do original é garantido que matematicamente não existem mais fatores ?
    – Isac
    3/09/2017 às 2:16
  • Isac, sim, exceto se esse fator for um número primo. Se um número a é composto, então ele é o produto de dois números onde ao menos um deles é menor ou igual que a sua raiz quadrada. 3/09/2017 às 2:34
  • Obrigado pela ajuda amigos, essas dicas de melhorias vão me ajudar no final do trabalho na análise assintótica ! 3/09/2017 às 2:43

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .