Cálculo do número primo?

@Cawende

O código abaixo identifica se é primo ou não:

public static void main(String[] args) {
    System.out.println("Digite um numero: ");
    int num = new Scanner(System.in).nextInt();
    boolean primo = false;
    for(int i = 2; i < num;i++){
        if(num%i==0){ // <<< De um foco nisto aqui
            primo = true;
        }
    }
    System.out.println((primo)? "é primo":"Não é primo");
}

A maneira mais simples de reduzir a quantidade de repetições para descobrir se um número N é primo é, ao invés de iterar de 2 até N, iterar de 2 até a raiz quadrada de N.

O “teste de primitividade” é algo complexo de se fazer.

Existem basicamente dois tipos de teste: Determinístico e Não determinístico.

O primeiro te diz com 100% de certeza se um número é primo ou não (é o que você está fazendo).

O segundo te dá uma porcentagem de chance de um número ser primo, mas te dá 100% de certeza que o número não é primo quando ele não é, compreende? Por exemplo, o número 7 é primo. Se você rodar um algoritmo probabilístico para determinar se 7 é primo, ele vai te dizer: Talvez, com 70% de chance. Agora se você rodar o mesmo algoritmo para um número que não é primo, como o 9, ele vai te dizer: Com certeza esse número não é primo.

A diferença entre os dois é que geralmente, o Não determinístico é extremamente mais eficiente do que o Determinístico.

Um algoritmo interessante para começar com análises probabilísticas é o de Miller-Rabin (lê o artigo, é bem curtinho e explica bem como funciona).

Se você tem um range de números e quer saber os primos que tem ali, você pode filtrar a lista inicialmente utilizando um algoritmo não determinístico e, depois, testar cada candidato com um algoritmo determinístico

Se você quer, por exemplo, descobrir todos os números primos entre 2000000 e 7000000, você pode fazer um loop de um número até o outro, utilizando o algoritmo de Miller-Rabin como primeiro teste para filtrar os provaveis primos. Depois, com uma lista de candidatos a números primos, você pode fazer o teste normal e ineficiente com o loop, testando os divisores de 2 até a raiz quadrada de cada candidato (determinístico).

Existem algoritmos não determinísticos bem mais complexos e que te dão uma porcentagem de certeza maior, o que pode diminuir ainda mais o tempo de execução.

Repare que ainda há a estrutura de repetição que você quer evitar, mas é executada bem menos vezes do que se você fosse resolver o problema só com ela. O teste determinístico também pode ser feito de maneira mais rápida. Olha essa parte de Fast Deterministic Tests do Wikipedia (só tem em inglês, se você não conseguir entender me avisa que eu traduzo).

Exemplos de implementação do algoritmo de Miller-Rabin: Primality_Testing

Espero ter ajudado!

minha dúvida é como elaborar um algoritmo que verifica se o número é primo ou nao sem estrutura de repetição

@Cawende então arrume a pergunta deste tópico.

é possível saber se um determinado número e primo ou não se usar as estrutura de repetição . se é como?