Java Program för att kontrollera primtal med exempel

Vad är ett primtal?

Ett primtal är ett naturligt tal större än 1 som bara är delbart med 1 eller sig självt. Till exempel är 11 bara delbart med 1 eller sig självt. Andra primtal är 2, 3, 5, 7, 11, 13, 17, och talföljden fortsätter utan slut.

Ett tal större än 1 som inte är primtal kallas ett sammansatt tal, eftersom det kan bestå av mindre faktorer. Värdet 9 är sammansatt eftersom det dividerar jämnt med 3, och 15 är sammansatt eftersom det dividerar jämnt med 3 och 5.

Obs: 0 och 1 är inte primtal. 2 är det enda jämna primtalet, och negativa värden betraktas aldrig som primtal.

Hur man kontrollerar om ett tal är primtal i Java

Verifieringsstrategin är ett enkelt delningstest. Ta kandidatvärdet, dividera det med varje mindre heltal i tur och ordning och undersök resten som returneras av moduloperatorn. En rest på noll bevisar att en divisor existerar, vilket omedelbart diskvalificerar talet.

Programlogik:

• Vi behöver dividera ett inmatat tal, säg 17, från värden 2 till 17 och kontrollera resten. Om resten är 0 är talet inte primtal.
• Inget tal är delbart med mer än hälften av sig självt. Så vi måste slinga genom bara numberToCheck/2Om ingången är 17, är hälften 8.5 och loopen kommer att iterera genom värdena 2 till 8.
• Om numberToCheck är helt delbart med ett annat tal sätts flaggan isPrime till false och slingan lämnas.

Två Java Funktionerna bär hela algoritmen. Moduloperatorn % returnerar resten av en heltalsdivision, och break Satsen stoppar loopen så snart svaret är känt, så inga onödiga iterationer utförs.

Java Program för att kontrollera om ett tal är primtal eller inte

Programmet nedan tilldelar värdet 17 till variabeln numberToCheck och skriver ut varje divisionssteg, så att du kan följa resonemanget rad för rad. Koden är redigerbar, så ändra värdet och kör det igen med ett sammansatt tal som 21 för att se motsatt 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");
    }
  }

Förväntad produktion:

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

Loopen stannar vid 8 eftersom 17 dividerat med 2 är lika med 8 i heltalsaritmetik. Eftersom ingen rest någonsin varit noll, behåller flaggan isPrime sitt initialvärde sant och det sista villkoret skriver ut det positiva resultatet.

Optimerad primtalkontroll med kvadratrotmetoden

Att dividera upp till hälften av talet är korrekt men slösaktigt. Om ett tal n har en divisor som är större än dess kvadratrot, måste den matchande meddivisorn vara mindre än kvadratroten, så den skulle redan ha upptäckts. Att kontrollera upp till √n ger därför samma svar med betydligt 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));
        }
    }
}

Produktion:

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

Skicket i * i <= n undviker ett flyttalsanrop till Math.sqrt, och steget 2 hoppar över varje jämn divisor. För ett värde som 1 000 003 utför den grundläggande loopen ungefär 500 000 iterationer medan den här versionen utför färre än 500.

Kontrollera ett primtal som angetts av användaren

Hårdkodad inmatning är praktisk för demonstrationer, men i verkliga övningar krävs oftast tangentbordsinmatning. Klassen Scanner läser ett heltal från konsolen och skickar det till samma isPrime-metod.

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

Provkörning:

Enter a number: 29
29 is a Prime number

Vanliga misstag när man skriver ett primtalsprogram

De flesta felaktiga inlämningar misslyckas på gränsvärden snarare än på huvudloopen. Listan nedan täcker de fel som förekommer oftast i nybörjarkod.

1. Börjar loopen vid 1: Varje heltal divideras med 1, så flaggan sätts omedelbart till falskt och programmet rapporterar att inget tal är primtal.
2. Behandlar 1 som ett primtal: Värdet 1 har bara en divisor, så det misslyckas med definitionen av tvådivisorer och måste returnera falskt.
3. Utelämnar break-satsen: Programmet returnerar fortfarande rätt svar, men det fortsätter att iterera efter att domen är känd, vilket slösar tid på stora indata.
4. Använda i <= n som gränsen: Talet dividerar alltid sig självt, så loopen måste sluta innan n når.
5. Jämförande med = istället för ==: Ett enda likhetstecken tilldelar ett värde snarare än att testa det, vilket producerar ett kompileringsfel i if-villkoret.

Jämförelse av Prime Checking-metoder

Välj den metod som matchar indatastorleken och om ett värde eller ett helt intervall måste testas.

När ett helt intervall måste klassificeras snarare än ett enda värde, är sikten mycket effektivare. Vårt kompletterande program för att hitta Prime Numbers från 1 till 100 visar det mönstret. För relaterade loopdrivna övningar, granska Fibonacci-serien i Java, den Java palindromprogram, Och den Bubble Sortera algoritm i JavaNybörjare som behöver repetition i att deklarera flaggan och kontringsspelet bör läsa om Java variabler i huvudsak Java handledning.

Vanliga frågor