Java Programma per verificare i numeri primi con esempio

Cos'è un numero primo?

Un numero primo è un numero naturale maggiore di 1 che è divisibile solo per 1 o per se stesso. Ad esempio, 11 è divisibile solo per 1 o per se stesso. Altri numeri primi sono 2, 3, 5, 7, 11, 13, 17 e la sequenza continua all'infinito.

Un numero maggiore di 1 che non è primo è detto numero composto, perché può essere composto da fattori più piccoli. Il valore 9 è composto perché è divisibile esattamente per 3, e 15 è composto perché è divisibile esattamente per 3 e 5.

Nota: 0 e 1 non sono numeri primi. 2 è l'unico numero primo pari e i valori negativi non sono mai considerati primi.

Come verificare se un numero è primo in Java

La strategia di verifica consiste in un semplice test di divisibilità. Si prende il valore candidato, lo si divide a turno per ciascun numero intero più piccolo e si esamina il resto restituito dall'operatore modulo. Un resto pari a zero dimostra che esiste un divisore, il che esclude immediatamente il numero.

Logica del programma:

• Dobbiamo dividere un numero dato, ad esempio 17, per i valori compresi tra 2 e 17 e controllare il resto. Se il resto è 0, il numero non è primo.
• Nessun numero è divisibile per più della metà di se stesso. Quindi dobbiamo farlo loop attraverso solo numberToCheck/2Se l'input è 17, la metà è 8.5 e il ciclo scorrerà i valori da 2 a 8.
• Se numberToCheck è completamente divisibile per un altro numero, il flag isPrime è impostato su false e si esce dal ciclo.

Due Java le caratteristiche trasportano l'intero algoritmo. L'operatore modulo % restituisce il resto di una divisione intera e il break L'istruzione interrompe il ciclo non appena si conosce la risposta, evitando così l'esecuzione di iterazioni non necessarie.

Java Programma per verificare se un numero è primo o meno

Il programma seguente assegna il valore 17 alla variabile numberToCheck e stampa ogni passaggio della divisione, in modo da poter seguire il ragionamento riga per riga. Il codice è modificabile, quindi cambia il valore ed eseguilo di nuovo con un numero composto come 21 per vedere il risultato opposto.

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

Uscita prevista:

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

Il ciclo si interrompe a 8 perché 17 diviso 2 è uguale a 8 nell'aritmetica intera. Poiché nessun resto è mai stato zero, il flag isPrime mantiene il suo valore iniziale di true e la condizione finale stampa il verdetto positivo.

Verifica ottimizzata dei numeri primi utilizzando il metodo della radice quadrata

Dividere fino a metà del numero è corretto ma inefficiente. Se un numero n ha un divisore maggiore della sua radice quadrata, il codivisore corrispondente deve essere minore della radice quadrata, quindi sarebbe già stato trovato. Verificare fino a √n produce quindi lo stesso risultato con molte meno iterazioni.

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

Produzione:

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

La condizione i * i <= n Evita una chiamata a Math.sqrt in virgola mobile e il passo di 2 salta ogni divisore pari. Per un valore come 1,000,003, il ciclo base esegue circa 500,000 iterazioni, mentre questa versione ne esegue meno di 500.

Verifica un numero primo inserito dall'utente

L'input codificato in modo statico è comodo per le dimostrazioni, ma gli esercizi reali di solito richiedono l'input da tastiera. La classe Scanner legge un numero intero dalla console e lo passa allo stesso metodo isPrime.

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

Esecuzione di esempio:

Enter a number: 29
29 is a Prime number

Errori comuni nella scrittura di un programma sui numeri primi

La maggior parte degli invii errati fallisce a causa dei valori limite piuttosto che nel ciclo principale. L'elenco seguente riporta gli errori che si verificano più frequentemente nel codice dei principianti.

1. Inizio del ciclo da 1: Ogni numero intero è divisibile per 1, quindi il flag viene impostato immediatamente su falso e il programma segnala che nessun numero è primo.
2. Considerando 1 come numero primo: Il valore 1 ha un solo divisore, quindi non soddisfa la definizione di due divisori e deve restituire false.
3. Omettendo l'istruzione break: Il programma restituisce comunque la risposta corretta, ma continua a iterare anche dopo che il verdetto è noto, il che spreca tempo con input di grandi dimensioni.
4. utilizzando i <= n come limite: Il numero è sempre divisibile per se stesso, quindi il ciclo deve interrompersi prima di raggiungere n.
5. Confronto con = invece di ==: Un singolo segno di uguale assegna un valore anziché verificarlo, il che produce un errore in fase di compilazione nella condizione if.

Confronto tra metodi di verifica della primalità

Scegli il metodo più adatto alla dimensione dei dati di input e alla necessità di testare un singolo valore o un intero intervallo.

Quando è necessario classificare un intero intervallo anziché un singolo valore, il setaccio è molto più efficiente. Il nostro programma complementare per trovare Prima Numbers da 1 a 100 dimostra quello schema. Per esercizi correlati basati su cicli, rivedere il serie di Fibonacci in Java, il Java programma palindromo Bubble Algoritmo di ordinamento in Java. I principianti che hanno bisogno di un ripasso sulla dichiarazione della bandiera e del contatore dovrebbero leggere di Java variabili nel principale Java lezione.

DOMANDE FREQUENTI