• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

joaorosa

[Resolvido] Verificar se um número é primo

16 mensagens neste tópico

boas malta.

eu gostava de saber se existe alguma função em java que verifique se um nº é primo...

cps

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

não conheço nenhuma e se existisse devia estar na classe Math e não encontrei lá nada.

mas encontras facilmente implementações dessa função na net (embora todas as que vi usavam algoritmos pouco eficientes).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

não sei como implementar em java, mas o método mais rápido que conheço e utilizo é:

verificar se é impar (se for par, ver se não é o 2) e depois fazer o módulo por todos os quadrados de numeros impares menores que o numero (os quadrados)...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu por acaso fiz um em Java a coisa de um ano mas quando o meu portátil se foi também o primo foi :)

Uma forma rápido de fazeres é o ciclo que faz o mod (%) do numero por 2,3,4 se nesse intervalo der algum mod = 0 então não é primo.

Há também uma regra com a raiz quadrada para reduzir a lista de procura mas não me lembro como é :S

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Há encontrei a regra da raiz que permite optimizar o programa. No fim deve ficar algo assim.

boolean primo(int n){
  if(n <= 3){
    return true;
  }
  for(int i = 3; i < Raiz(n);i=+2){
    if(n % i == 0){
      return false;
    }
  }
  return true;
}

Há um método que faz a raiz na lib Math do Java mas não me lembro como é :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

desde quando é que o 1 é primo? esse if(n<=3) não está aí muito bem...

EDIT: para n=4, 6 e 8, qual era o resultado que o programa ia dar? o ciclo tem que começar em 2 e não em 3.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

o ciclo tem de começar no 3 e implementar 2 de cada vez, já que qualquer numero par é divisivel por 2, logo não é primo...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

o ciclo tem de começar no 3 e implementar 2 de cada vez, já que qualquer numero par é divisivel por 2, logo não é primo...

o problema é que ele não verificou se era par antes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

desde quando é que o 1 é primo? esse if(n<=3) não está aí muito bem...

Isso depende há fontes que dizem que o 0 e 1 não são primos outras dizem que o 1 é logo se o 1 , 2 e 3 são é lógico que comece o ciclo em 3.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

desde quando é que o 1 é primo? esse if(n<=3) não está aí muito bem...

Isso depende há fontes que dizem que o 0 e 1 não são primos outras dizem que o 1 é logo se o 1 , 2 e 3 são é lógico que comece o ciclo em 3.

actualmente acho que muito dificilmente encontras fontes que considerem o 1 como primo.

primeiro porque o 1 tem apenas um divisor e para ser primo deveria ter dois, além disso não era conveniente que o 1 fosse primo, visto que alguns teoremas passariam a ser falsos se o 1 fosse primo (como por exemplo o Teorema Fundamental da Aritmética).

quanto ao 0, 0 a dividir por qualquer número dá resto 0, logo 0 tem infinitos divisores e como tal também não é primo (mas normalmente quando se fala em números primos considera-se apenas o conjunto dos inteiros positivos).

executa esse teu programa para o 4, o 6 e o 8 e vê qual é o resultado que obténs. estás a começar o ciclo em 3 e a acabar em sqrt(n), como sqrt( 8 )<3 nem chegas a entrar no ciclo para valores até 8, ou seja, a tua função vai dizer que os números são primos.

e para todos os números pares que só tenham 4 divisores o teu algoritmo vai falhar (visto que um divisor é o 2, divisor esse que tu não estás a verificar, e o outro é maior do que a raiz quadrada do número).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

tens razão quanto à raiz quadrada... deveria ser o quadrado e não a raiz...

quanto aos numeros pares, não há necessidade de os verificar... se são divisiveis por dois, não podem ser primos...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

tens razão quanto à raiz quadrada... deveria ser o quadrado e não a raiz...

quanto aos numeros pares, não há necessidade de os verificar... se são divisiveis por dois, não podem ser primos...

vocês não estão a perceber o que eu escrevo. a raíz quadrada está correcta, e o iniciar o ciclo com o valor 3 estaria certo se se verificasse antes se o número é par!

tal como disseste se são pares, são divisíveis por 2, logo não são primos, mas é preciso ver se são pares!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

se n começa num numero impar e faz incrementos de 2, nunca tem valor par... então, verificar para quê?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acertem lá as agulhas em rela.ção ao algoritmo :)

Existem várias formas de verificar se um número é primo ou não, estou a lembrar-me do Crivo de Eratóstenes por exemplo. Umas formas melhores, outras nem por isso, mas respondendo ao tópico.

Não existe, que eu conheça, na API standard do Java função para verificar se um número é primo ou não. Esse é um tipo de problema que normalmente não vem incluído nas bibliotecas das linguagens. No entanto é um problema tão comum ou tão badalado que certamente alguém já o implementou, é uma questão de fazer uma ou duas pesquisas, ou então esperar que estes jovens se decidam com o algoritmo... o que pode levar um tempo :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Copiei isto daqui: http://www.computing.net/programming/wwwboard/forum/11287.html

É o último tópico à data e parece que funciona correctamente, feito em por um português e tudo :D

import java.util.Random;

public class s5ex1 {

public static void main(String[] args) {

    Random r=new Random();
    int a=r.nextInt();

    if (a%2==0) {
        System.out.println("numero "+a+" nao é primo");
    }
    else {
        int b=a;
        int c=b+20;
        while (b<c){
            if (a%b==0 && a%a==0){
                System.out.println("numero "+a+" é primo");
                break;
           }
           else {
              b=b+1;
           }
       }
      
     if (b>=c){
         System.out.println("numero "+a+" nao é primo");
     }

Aqui tens mais uma opção, feita pela sun, no site: http://java.sun.com/developer/JDCTechTips/2002/tt0806.html

A classe original tem como objectivo criar números primos, eu deixo aqui apenas o método que permite determinar se o número é primo ou não.

static boolean isPrime(int n) {
    
            // 2 is the smallest prime
    
            if (n <= 2) {
                return n == 2;
            }
    
            // even numbers other than 2 are not prime
    
            if (n % 2 == 0) {
                return false;
            }
    
            // check odd divisors from 3
            // to the square root of n
    
            for (int i = 3, end = (int)Math.sqrt(n);
            i <= end; i += 2) {
                if (n % i == 0) {
                    return false;
                }
            }
    
            return true;
        }

Pode ser que ajude....

Prometo que é a última alteração que faço a esta resposta :)

Estive a ver a API e lembrei-me que a classe Math tem um irmãozinho muitas vezes esquecido, o BigInteger. Esta classe tem um método, o isProbablePrime() que te permite determinar se um número é provávelmente um primo ou se de certeza absoluta não é. O parâmetro de entrada é o grau de certeza com que queres testar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora