Java Program do sprawdzania liczb pierwszych z przykładem

Co to jest liczba pierwsza?

Liczba pierwsza to liczba naturalna większa od 1, która jest podzielna tylko przez 1 lub przez samą siebie. Na przykład 11 jest podzielne tylko przez 1 lub przez samą siebie. Inne liczby pierwsze to 2, 3, 5, 7, 11, 13, 17 i ciąg ten ciągnie się bez końca.

Liczba większa od 1, która nie jest liczbą pierwszą, nazywana jest liczbą złożoną, ponieważ można ją rozłożyć na mniejsze czynniki. Liczba 9 jest liczbą złożoną, ponieważ dzieli się równo przez 3, a 15 jest liczbą złożoną, ponieważ dzieli się równo przez 3 i 5.

Uwaga: 0 i 1 nie są liczbami pierwszymi. 2 jest jedyną parzystą liczbą pierwszą, a wartości ujemne nigdy nie są uważane za liczby pierwsze.

Jak sprawdzić, czy liczba jest liczbą pierwszą w Java

Strategia weryfikacji to prosty test podzielności. Weź wartość kandydata, podziel ją przez każdą mniejszą liczbę całkowitą po kolei i sprawdź resztę zwróconą przez operator dzielenia. Reszta równa zero dowodzi istnienia dzielnika, co natychmiast dyskwalifikuje liczbę.

Logika programu:

• Musimy podzielić liczbę wejściową, powiedzmy 17, przez wartości od 2 do 17 i sprawdzić resztę. Jeśli reszta wynosi 0, liczba nie jest pierwsza.
• Żadna liczba nie jest podzielna przez więcej niż połowę samej siebie. Więc musimy pętla przez właśnie numberToCheck/2. Jeśli wartość wejściowa wynosi 17, połowa wynosi 8.5, a pętla będzie iterować przez wartości od 2 do 8.
• Jeżeli liczba „liczba do sprawdzenia” jest całkowicie podzielna przez inną liczbę, flaga „jestPierwsza” jest ustawiana na false i pętla zostaje zamknięta.

dwa Java cechy niosą ze sobą cały algorytm. Operator modulo % zwraca resztę z dzielenia liczb całkowitych i break Instrukcja zatrzymuje pętlę natychmiast po poznaniu odpowiedzi, dzięki czemu nie są wykonywane żadne zbędne iteracje.

Java Program sprawdzający, czy liczba jest pierwsza czy nie

Poniższy program przypisuje wartość 17 zmiennej numberToCheck i wyświetla każdy krok dzielenia, dzięki czemu można śledzić przebieg rozumowania wiersz po wierszu. Kod jest edytowalny, więc zmień wartość i uruchom go ponownie z liczbą złożoną, taką jak 21, aby zobaczyć odwrotny wynik.

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

Oczekiwany wynik:

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

Pętla zatrzymuje się na 8, ponieważ 17 podzielone przez 2 równa się 8 w arytmetyce liczb całkowitych. Ponieważ żadna reszta nie była równa zero, flaga isPrime zachowuje swoją początkową wartość true, a warunek końcowy wyświetla pozytywny werdykt.

Zoptymalizowane sprawdzanie liczb pierwszych metodą pierwiastka kwadratowego

Dzielenie do połowy liczby jest poprawne, ale nieekonomiczne. Jeśli liczba n ma dzielnik większy od pierwiastka kwadratowego, odpowiadający mu współdzielnik musi być mniejszy od pierwiastka kwadratowego, więc zostałby już odkryty. Sprawdzenie do √n daje zatem ten sam wynik przy znacznie mniejszej liczbie iteracji.

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

Wyjście:

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

Warunek i * i <= n unika wywołania funkcji Math.sqrt dla liczb zmiennoprzecinkowych, a krok 2 pomija każdy parzysty dzielnik. Dla wartości takiej jak 1 000 003 podstawowa pętla wykonuje około 500 000 iteracji, podczas gdy ta wersja wykonuje ich mniej niż 500.

Sprawdź liczbę pierwszą wprowadzoną przez użytkownika

Zakodowane na stałe dane wejściowe są wygodne w demonstracjach, jednak w rzeczywistych ćwiczeniach zazwyczaj wymagane jest wprowadzanie danych z klawiatury. Klasa Scanner odczytuje liczbę całkowitą z konsoli i przekazuje ją do tej samej metody 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();
    }
}

Przykładowy przebieg:

Enter a number: 29
29 is a Prime number

Typowe błędy przy pisaniu programu do obliczania liczb pierwszych

Większość niepoprawnych przesłań kończy się niepowodzeniem na wartościach granicznych, a nie w pętli głównej. Poniższa lista zawiera błędy, które najczęściej pojawiają się w kodzie dla początkujących.

1. Rozpoczęcie pętli od 1: Każda liczba całkowita dzieli się przez 1, więc flaga jest natychmiast ustawiana na fałsz, a program informuje, że żadna liczba nie jest liczbą pierwszą.
2. Traktowanie 1 jako liczby pierwszej: Wartość 1 ma tylko jeden dzielnik, więc nie spełnia definicji dzielnika dwudzielnego i musi zwrócić fałsz.
3. Pominięcie instrukcji break: Program nadal zwraca prawidłową odpowiedź, ale po poznaniu werdyktu powtarza działanie, co powoduje stratę czasu przy dużych nakładach.
4. Korzystanie z i <= n jako ograniczenie: Liczba ta zawsze dzieli się sama, więc pętla musi się zatrzymać przed osiągnięciem n.
5. Porównując z = zamiast ==: Pojedynczy znak równości przypisuje wartość zamiast ją testować, co powoduje błąd kompilacji w warunku if.

Porównanie metod sprawdzania liczb pierwszych

Wybierz metodę odpowiadającą rozmiarowi danych wejściowych i określ, czy testowaniu ma podlegać jedna wartość czy cały zakres.

Gdy trzeba sklasyfikować cały zakres, a nie pojedynczą wartość, sito jest znacznie bardziej wydajne. Nasz program towarzyszący do wyszukiwania premia Numbers od 1 do 100 demonstruje ten wzór. Aby zapoznać się z powiązanymi ćwiczeniami opartymi na pętlach, przejrzyj Ciąg Fibonacciego w JavaThe Java program palindromowyi Bubble Algorytm sortowania w JavaPoczątkujący, którzy potrzebują przypomnienia na temat deklarowania flagi i kontry, powinni przeczytać o Java zmienne głównie Java Tutorial.

FAQ