GUJ Discussões   :   últimos tópicos   |   categorias   |   GUJ Respostas

Fatoração e calculo de número primo [SOLUÇÃO]


#1

Ajudando um usuário do fórum a resolver um problema acabei pesquisando na net sobre fatoração e números primos.

Descrobri que não existe muita coisa em java consistente sobre isso, como consegui desenvolver uma solução quase perfeita (mesmo a API do java não possui uma classe que dá 100% de certeza se o número é primo) e não existe na API um método que ache o próximo número primo de um certo número.

Levo em consideração que vc sabe fazer validações básicas, String, inteito etc.

Usei recursividade, então é uma boa pra rodar em modo debug....

public class CalculaFatoracao {
	// Variáveis globais
	static int divisor = 2;
	public static void main(String[] args) {
		// Vetor de inteiros
		int[] vetor = new int[] { 12, 61, 16, 43, 56, 32, 8, 90, 140, 960 };
		new CalculaFatoracao().fatorar(vetor);
	}
	// Fatora o vetor de inteiros passado e calcula o MMC (máximo múltiplo comum)
	public void fatorar(int[] valores){
		int cont;		
		int mudaDividor;
		int mmc = 1;
		String expoente = "";
		String saida;
		for (int i = 0; i < valores.length; i++) {
			System.out.printf("\t%d", valores[i]);			
		}
		do {
			cont = 0;
			mudaDividor = 0;
			saida = "";
			// Percorre o vetor de inteiros
			for (int i = 0; i < valores.length; i++) {
				// Se o resto da divisão do valor atual do vetor pelo divisor for zero efetuar a divisão 
				if (valores[i] % divisor == 0) {
					valores[i] = valores[i] / divisor;
					// Guardando o expoente usado na divião
					expoente = ""+divisor;
				// Senão incremente a variável mudaDivisor 
				// Usada para determinar se o divisor será mudado
				}else{					
					mudaDividor++; 
				}
				saida += "\t" + valores[i];
				// Somando o total do vetor
				cont += valores[i];
			}
			saida = "\t\t" + expoente + "\n" + saida;
			// Se a variável mudaDivisor for igual ao tamanho do vetor significa que não houve divisão
			// na interação do for e que o divisor deve ser mudado para o próximo número primo
			if (mudaDividor == valores.length) {				
				divisor = proximoPrimo(divisor);
			// Senão calcula parcialmente o MMC e imprime a linha
			}else{
				mmc *= divisor;
				System.out.printf("%s", saida);				
			}
		// Enquanto a soma dos valores do vetor for maior que o tamanho do vetor executa o laço
		// Quando as divisões acabarem a soma dos valores do vetor será igual ao tamanho do vetor
		// indicando que a fotoração chegou ao fim
		} while (cont > valores.length);
		System.out.printf("\n\n\tMMC: %d\n", mmc);
	}
	/**
	 * Método para calcular o próximo número primo, dado um número como entrada
	 * Usa recursividade
	 * 
	 * @param numero
	 * @return int
	 */
	public int proximoPrimo(int numero) {
		/* Sobre números primos:
		 * Para saber se um número é primo, dividimos esse número pelos números primos 2, 3, 5, 7, 11 etc,
		 * Até que tenhamos:
         *   =>  ou uma divisão com resto zero e neste caso o número não é primo,
         *   =>  ou uma divisão com quociente menor que o divisor e o resto diferente de zero. Neste caso o número é primo.   
		 * */
		// Incrementa o valor passado em 1
		int proximo = numero + 1;
		int soma = 0;		
		int retorno = proximo;
		String aux = proximo + "";
		Character c;
		// Efetua a soma dos valores das posições do proximo
		// Ex. 23: 	2 + 3 = 5
		// Ex. 125:	1 + 2 + 5 = 8
		for (int i = 0; i < aux.length(); i++) {
			c = aux.charAt(i);
			soma += Integer.parseInt(c.toString());
		}
		// Se o proximo for divisivel por 2 chama o método proximoPrimo com o valor da variável proximo
		if (proximo % 2 == 0) {
			retorno = proximoPrimo(proximo);
		// Verifica se a soma dos valores das posições do númeto é divisivel por 3
		// Exclui o caso da soma ser 3 pois nesta caso 3 é primo
		} else if (soma % 3 == 0 && proximo != 3) {
			retorno = proximoPrimo(proximo);
		// Verifica se a última posição do número é igual a 0 ou 5
		// Exclui o caso do número ter uma posição e ser 5 pois 5 é primo 
		} else if (aux.substring(aux.length() - 1, aux.length()).equals("0") && aux.length() > 1
				|| aux.substring(aux.length() - 1, aux.length()).equals("5") && aux.length() > 1 ) {
			retorno = proximoPrimo(proximo);
		} else {
			// Passando pelas validações acima é preciso testar a divisão do 
			// número com os valores acima de 5, ou seja, 7, 9, 11....
			// Calculando a raiz quadrada do número, truncando para inteiro
			int raiz = (int) Math.sqrt(proximo);
			// A matemática diz que só é preciso testar a divisão até a raiz quadrada 
			// do número para saber se o mesmo é primo  
			for (int i = 7; i <= raiz; i++) {
				// Se o resto da divião for zero significa que ele não é primo, então chama o método 
				// proximoPrimo com o valor da variável proximo
				if (proximo % i == 0) {
					i = raiz;
					retorno = proximoPrimo(proximo);
				}
			}			
		}
		return retorno;
	}
}

flws... :arrow:


#2