Java Program til at kontrollere primtal med eksempel

Hvad er et primtal?

Et primtal er et naturligt tal større end 1, der kun er deleligt med 1 eller sig selv. For eksempel er 11 kun deleligt med 1 eller sig selv. Andre primtal er 2, 3, 5, 7, 11, 13, 17, og talfølgen fortsætter uendeligt.

Et tal større end 1, som ikke er primtal, kaldes et sammensat tal, fordi det kan være sammensat af mindre faktorer. Værdien 9 er sammensat, fordi den dividerer ligeligt med 3, og værdien 15 er sammensat, fordi den dividerer ligeligt med 3 og 5.

Bemærk: 0 og 1 er ikke primtal. 2 er det eneste lige primtal, og negative værdier betragtes aldrig som primtal.

Sådan tjekker du om et tal er et primtal Java

Verifikationsstrategien er en ligetil delelighedstest. Tag kandidatværdien, divider den med hvert mindre heltal efter tur, og undersøg resten, der returneres af modulusoperatoren. En rest på nul beviser, at der findes en divisor, hvilket øjeblikkeligt diskvalificerer tallet.

Program logik:

• Vi skal dividere et inputtal, f.eks. 17, fra værdierne 2 til 17 og kontrollere resten. Hvis resten er 0, er tallet ikke et primtal.
• Intet tal er deleligt med mere end halvdelen af ​​sig selv. Så det er vi nødt til loop lige igennem numberToCheck/2Hvis inputtet er 17, er halvdelen 8.5, og løkken vil iterere gennem værdierne 2 til 8.
• Hvis talTilKontrollering er fuldstændig deleligt med et andet tal, sættes flaget isPrime til false og løkken forlades.

to Java Funktioner bærer hele algoritmen. Moduloperatoren % returnerer resten af ​​en heltalsdivision, og break Sætningen stopper løkken, så snart svaret er kendt, så der ikke udføres unødvendige iterationer.

Java Program til at kontrollere om et tal er primtal eller ej

Programmet nedenfor tildeler værdien 17 til variablen numberToCheck og udskriver hvert divisionstrin, så du kan følge argumentationen linje for linje. Koden kan redigeres, så skift værdien og kør den igen med et sammensat tal som f.eks. 21 for at se det modsatte resultat.

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

Forventet output:

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

Løkken stopper ved 8, fordi 17 divideret med 2 er lig med 8 i heltalsregning. Da ingen rest nogensinde har været nul, beholder flaget isPrime sin oprindelige værdi, som er sand, og den sidste betingelse udskriver den positive dom.

Optimeret primtalkontrol ved hjælp af kvadratrodsmetoden

Det er korrekt, men spild af tid at dividere op til halvdelen af ​​tallet. Hvis et tal n har en divisor, der er større end kvadratroden, skal den tilsvarende meddivisor være mindre end kvadratroden, så den ville allerede være opdaget. At tjekke op til √n giver derfor det samme svar med langt færre iterationer.

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

Output:

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

Betingelsen i * i <= n undgår et flydende kommakald til Math.sqrt, og trinnet 2 springer alle lige divisorer over. For en værdi som 1,000,003 udfører den grundlæggende løkke cirka 500,000 iterationer, mens denne version udfører færre end 500.

Kontroller et primtal indtastet af brugeren

Hardkodet input er praktisk til demonstrationer, men i virkelige øvelser kræves der normalt tastaturinput. Scanner-klassen læser et heltal fra konsollen og sender det til den samme isPrime-metode.

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

Prøvekørsel:

Enter a number: 29
29 is a Prime number

Almindelige fejl ved skrivning af et primtalprogram

De fleste forkerte indsendelser fejler på grænseværdier snarere end på hovedløkken. Listen nedenfor dækker de fejl, der oftest optræder i begynderkode.

1. Start af løkken ved 1: Hvert heltal divideres med 1, så flaget sættes til falsk med det samme, og programmet rapporterer, at intet tal er primtal.
2. Behandling af 1 som et primtal: Værdien 1 har kun én divisor, så den opfylder ikke definitionen af ​​to divisorer og skal returnere falsk.
3. Udeladelse af break-sætningen: Programmet returnerer stadig det rigtige svar, men det fortsætter med at iterere, efter at konklusionen er kendt, hvilket spilder tid på store input.
4. Ved brug af i <= n som grænsen: Tallet dividerer altid sig selv, så løkken skal stoppe, før den når n.
5. Sammenligning med = i stedet for ==: Et enkelt lighedstegn tildeler en værdi i stedet for at teste den, hvilket producerer en kompileringsfejl i if-betingelsen.

Sammenligning af Prime Checking-metoder

Vælg den metode, der matcher størrelsen af ​​inputtet, og om én værdi eller et helt interval skal testes.

Når et helt interval skal klassificeres i stedet for en enkelt værdi, er sigten langt mere effektiv. Vores ledsagende program til at finde Prime Numbers fra 1 til 100 demonstrerer dette mønster. For relaterede loop-drevne øvelser, gennemgå Fibonacci-rækken i Java, Java palindromprogram, og Bubble Sorter algoritme ind JavaBegyndere, der har brug for en genopfriskning af flagets og kontringernes deklaration, bør læse om Java variabler hovedsageligt Java tutorial.

Ofte Stillede Spørgsmål