Java Program de verificare a numărului prim cu exemplu

Ce este un număr prim?

Un număr prim este un număr natural mai mare decât 1, care este divizibil doar cu 1 sau cu el însuși. De exemplu, 11 este divizibil doar cu 1 sau cu el însuși. Alte numere prime sunt 2, 3, 5, 7, 11, 13, 17, iar secvența continuă la nesfârșit.

Un număr mai mare decât 1 care nu este prim se numește număr compozit, deoarece poate fi compus din factori mai mici. Valoarea 9 este compusă deoarece se divide în mod egal la 3, iar 15 este compusă deoarece se divide în mod egal la 3 și 5.

Notă: 0 și 1 nu sunt numere prime. 2 este singurul număr prim par, iar valorile negative nu sunt niciodată considerate prime.

Cum să verifici dacă un număr este prim în Java

Strategia de verificare este un test de divizibilitate simplu. Luați valoarea candidată, împărțiți-o pe rând la fiecare număr întreg mai mic și inspectați restul returnat de operatorul modul. Un rest de zero dovedește că există un divizor, ceea ce descalifică imediat numărul.

Logica programului:

• Trebuie să împărțim un număr introdus, să zicem 17, la valorile de la 2 la 17 și să verificăm restul. Dacă restul este 0, numărul nu este prim.
• Niciun număr nu este divizibil cu mai mult de jumătate din el însuși. Deci trebuie buclă prin doar numberToCheck/2Dacă intrarea este 17, jumătatea este 8.5 și bucla va itera prin valorile de la 2 la 8.
• Dacă numberToCheck este complet divizibil cu un alt număr, steagul isPrime este setat la false iar bucla este ieșită.

Doi Java caracteristicile poartă întregul algoritm. Operatorul modul % returnează restul unei împărțiri întreage și break Instrucțiunea oprește bucla imediat ce răspunsul este cunoscut, astfel încât să nu fie executate iterații inutile.

Java Program pentru a verifica dacă un număr este prim sau nu

Programul de mai jos atribuie valoarea 17 variabilei numberToCheck și afișează fiecare pas de împărțire, astfel încât să puteți urmări raționamentul linie cu linie. Codul este editabil, așa că schimbați valoarea și rulați-l din nou cu un număr compus, cum ar fi 21, pentru a vedea rezultatul opus.

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");
    }
  }

Ieșire preconizată:

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

Bucla se oprește la 8 deoarece 17 împărțit la 2 este egal cu 8 în aritmetica numerelor întregi. Deoarece nicio rest nu a fost vreodată zero, indicatorul isPrime își păstrează valoarea inițială, true, iar condiția finală afișează verdictul pozitiv.

Verificarea optimizată a numerelor prime folosind metoda rădăcinii pătrate

Împărțirea până la jumătate a numărului este corectă, dar risipitoare. Dacă un număr n are un divizor mai mare decât rădăcina sa pătrată, coîmpărțitorul corespunzător trebuie să fie mai mic decât rădăcina pătrată, deci ar fi fost deja descoperit. Prin urmare, verificarea până la √n produce același răspuns cu mult mai puține iterații.

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));
        }
    }
}

ieșire:

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

Conditia i * i <= n evită un apel în virgulă mobilă către Math.sqrt, iar pasul de 2 omite fiecare divizor par. Pentru o valoare precum 1,000,003, bucla de bază efectuează aproximativ 500,000 de iterații, în timp ce această versiune efectuează mai puțin de 500.

Verificarea unui număr prim introdus de utilizator

Introducerea de date în cod fix este convenabilă pentru demonstrații, însă exercițiile reale solicită de obicei introducerea de date de la tastatură. Clasa Scanner citește un număr întreg din consolă și îl transmite aceleiași metode 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();
    }
}

Executare eșantion:

Enter a number: 29
29 is a Prime number

Greșeli frecvente la scrierea unui program cu numere prime

Majoritatea trimiterilor incorecte eșuează la valorile limită, mai degrabă decât la bucla principală. Lista de mai jos prezintă erorile care apar cel mai des în codul pentru începători.

1. Începând bucla de la 1: Fiecare număr întreg se divide la 1, deci steagul este setat imediat pe fals și programul raportează că niciun număr nu este prim.
2. Tratând 1 ca număr prim: Valoarea 1 are un singur divizor, deci nu îndeplinește definiția cu doi divizori și trebuie să returneze fals.
3. Omiterea instrucțiunii break: Programul returnează în continuare răspunsul corect, dar continuă să iterateze după ce verdictul este cunoscut, ceea ce pierde timp cu intrări mari.
4. Utilizarea i <= n ca limită: Numărul se divide întotdeauna pe sine, deci bucla trebuie să se oprească înainte de a ajunge la n.
5. Comparand cu = în loc de ==: Un singur semn egal atribuie o valoare în loc să o testeze, ceea ce produce o eroare la compilare în condiția if.

Compararea metodelor de verificare a primelor

Alegeți metoda care corespunde dimensiunii intrării și dacă trebuie testată o singură valoare sau un interval întreg.

Când trebuie clasificată o gamă întreagă în loc de o singură valoare, sita este mult mai eficientă. Programul nostru însoțitor pentru a găsi Prim Numbers de la 1 la 100 demonstrează acest model. Pentru exerciții similare bazate pe bucle, consultați Seria Fibonacci în Java, Java program palindrom, Şi Bubble Sortați algoritmul JavaÎncepătorii care au nevoie de o reîmprospătare a noțiunilor despre declararea steagului și contraatac ar trebui să citească despre Java variabile în principal Java tutorial.

Întrebări frecvente