Java Program pro kontrolu prvočísla s příkladem

Co je prvočíslo?

Prvočíslo je přirozené číslo větší než 1, které je dělitelné pouze 1 nebo samo sebou. Například 11 je dělitelné pouze 1 nebo samo sebou. Další prvočísla jsou 2, 3, 5, 7, 11, 13, 17 a tato posloupnost pokračuje donekonečna.

Číslo větší než 1, které není prvočíslo, se nazývá složené číslo, protože ho lze složit z menších činitelů. Číslo 9 je složené, protože se dělí rovnoměrně 3, a číslo 15 je složené, protože se dělí rovnoměrně 3 a 5.

Poznámka: 0 a 1 nejsou prvočísla. 2 je jediné sudé prvočíslo a záporné hodnoty se nikdy nepovažují za prvočísla.

Jak zkontrolovat, zda je číslo prvočíslo Java

Ověřovací strategie je jednoduchý test dělitelnosti. Vezměte kandidátskou hodnotu, postupně ji vydělte každým menším celým číslem a zkontrolujte zbytek vrácený operátorem modulu. Zbytek nula dokazuje existenci dělitele, což číslo okamžitě diskvalifikuje.

Programová logika:

• Potřebujeme vydělit vstupní číslo, řekněme 17, hodnotami od 2 do 17 a zkontrolovat zbytek. Pokud je zbytek 0, číslo není prvočíslo.
• Žádné číslo není dělitelné více než polovinou sebe sama. Takže musíme smyčka přes jen numberToCheck/2Pokud je vstup 17, polovina je 8.5 a smyčka bude iterovat hodnotami 2 až 8.
• Pokud je numberToCheck zcela dělitelné jiným číslem, příznak isPrime se nastaví na false a smyčka je opuštěna.

Dvě Java Funkce nesou celý algoritmus. Operátor modulu % vrací zbytek po celočíselném dělení a break Příkaz zastaví smyčku, jakmile je známa odpověď, takže se neprovádějí žádné zbytečné iterace.

Java Program pro kontrolu, zda je číslo prvočíslo či nikoli

Následující program přiřadí proměnné numberToCheck hodnotu 17 a vypíše každý krok dělení, takže můžete sledovat uvažování řádek po řádku. Kód je upravitelný, takže změňte hodnotu a spusťte jej znovu se složeným číslem, například 21, abyste viděli opačný výsledek.

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

Očekávaný výstup:

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

Smyčka se zastaví na čísle 8, protože 17 děleno 2 se v celočíselné aritmetice rovná 8. Protože žádný zbytek nebyl nikdy nula, příznak isPrime si ponechává počáteční hodnotu true a konečná podmínka vypíše kladný výsledek.

Optimalizovaná kontrola prvočísel pomocí metody druhé odmocniny

Dělení čísla až do poloviny je správné, ale nehospodárné. Pokud má číslo n dělitele většího než jeho druhá odmocnina, musí být odpovídající spoludělitel menší než druhá odmocnina, takže by již byl objeven. Kontrola až do √n proto vede ke stejnému výsledku s mnohem menším počtem iterací.

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

Výstup:

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

Kondice i * i <= n Vyhýbá se volání funkce Math.sqrt s plovoucí desetinnou čárkou a krok 2 přeskakuje každého sudého dělitele. Pro hodnotu jako 1 000 003 provede základní smyčka zhruba 500 000 iterací, zatímco tato verze provede méně než 500.

Kontrola prvočísla zadaného uživatelem

Pevně ​​zadaný vstup je vhodný pro demonstrace, ale skutečná cvičení obvykle vyžadují vstup z klávesnice. Třída Scanner načte celé číslo z konzole a předá ho téže metodě 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();
    }
}

Ukázkový běh:

Enter a number: 29
29 is a Prime number

Časté chyby při psaní programu pro prvočísla

Většina chybných odeslání selže na hraničních hodnotách spíše než v hlavní smyčce. Níže uvedený seznam zahrnuje chyby, které se nejčastěji objevují v kódu pro začátečníky.

1. Spuštění smyčky od 1: Každé celé číslo se dělí 1, takže příznak se okamžitě nastaví na hodnotu false a program hlásí, že žádné číslo není prvočíslo.
2. Považání 1 za prvočíslo: Hodnota 1 má pouze jednoho dělitele, takže nesplňuje definici dvou dělitelů a musí vrátit hodnotu false.
3. Vynechání příkazu break: Program stále vrací správnou odpověď, ale iteruje i poté, co je verdikt znám, což ztrácí čas na velkých vstupech.
4. Použití i <= n jako hranice: Číslo se vždy dělí samo sebou, takže smyčka se musí zastavit před dosažením n.
5. Srovnání s = místo ==: Jediné znaménko rovnosti přiřadí hodnotu, nikoli ji otestuje, což v podmínce if způsobí chybu při kompilaci.

Porovnání metod kontroly primárních zdrojů

Vyberte metodu, která odpovídá velikosti vstupu a tomu, zda je třeba testovat jednu hodnotu nebo celý rozsah.

Pokud je třeba klasifikovat celý rozsah, nikoli pouze jednu hodnotu, je síto mnohem efektivnější. Náš doprovodný program pro nalezení pojistné Numbers od 1 do 100 demonstruje tento vzorec. Související cvičení řízená smyčkami naleznete v Fibonacciho řada v Javase Java palindromový programA Bubble Algoritmus řazení v JavaZačátečníci, kteří si potřebují osvěžit znalosti o deklaraci příznaku a počítadla, by si měli přečíst o Java proměnné v hlavním Java konzultace.

Nejčastější dotazy