Java Program do drukowania Prime Numbers od 1 do 100

Co to jest liczba pierwsza?

A Liczba pierwsza Liczba pierwsza to liczba podzielna tylko przez jeden lub przez samą siebie. Jest to liczba naturalna większa od jeden, która nie jest iloczynem dwóch mniejszych liczb naturalnych. Na przykład 11 jest podzielne tylko przez jeden lub przez samą siebie. Inne liczby pierwsze to 2, 3, 5, 7, 11, 13, 17 i tak dalej.

Uwaga: 0 i 1 nie są liczbami pierwszymi. 2 jest jedyną parzystą liczbą pierwszą.

Między 1 a 100 istnieje dokładnie 25 liczb pierwszych. Poniższa tabela grupuje je według dekad, co uwidacznia wzór przerzedzania się wraz ze wzrostem wartości.

Jak wydrukować Prime Numbers Od 1 do 100 Program w Java

Poniżej znajduje się Java program do drukowania liczb pierwszych od 1 do 100:

Logika programu:

• Główną metodą program liczb pierwszych w Java zawiera pętlę, która sprawdza kolejno liczby pierwsze od 1 do 100.
• Metoda główna wywołuje metodę CheckPrime aby określić, czy liczba jest liczbą pierwszą Java lub nie.
• 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. Dlatego musimy wykonać pętlę po prostu dla funkcji numberToCheck/2. Jeśli wartość wejściowa to 17, połowa to 8.5, a pętla będzie iterować po wartościach od 2 do 8.
• If numberToCheck jest podzielne przez inną liczbę w całości, zwracamy fałsz i pętla zostaje przerwana.
• If numberToCheck jest liczbą pierwszą, zwracamy wartość true.
• W metodzie głównej dla liczb pierwszych od 1 do 100 w Java, sprawdź czy isPrime jest TRUE i dodaj wartość do liczby pierwszejNumbersZnaleziono ciąg znaków.
• Na koniec wydrukuj liczby pierwsze od 1 do 100 w Java.

Oddzielenie kontroli do osobnej metody sprawia, że ​​program jest wielokrotnego użytku. Tę samą metodę CheckPrime można wywołać z dowolnym górnym limitem, po prostu zmieniając zmienną maxCheck.

public class PrimeNumbers {

    public static void main(String[] args) {

        int i;
        int num = 0;
        int maxCheck = 100; // maxCheck limit till which you want to find prime numbers
        boolean isPrime = true;

        //Empty String
        String primeNumbersFound = "";

        //Start loop 2 to maxCheck
        for (i = 2; i <= maxCheck; i++) {
            isPrime = CheckPrime(i);
            if (isPrime) {
                primeNumbersFound = primeNumbersFound + i + " ";
            }
        }
        System.out.println("Prime numbers from 1 to " + maxCheck + " are:");
        // Print prime numbers from 1 to maxCheck
        System.out.println(primeNumbersFound);
    }
    public static boolean CheckPrime(int numberToCheck) {
        int remainder;
        for (int i = 2; i <= numberToCheck / 2; i++) {
            remainder = numberToCheck % i;
            //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
            if (remainder == 0) {
                return false;
            }
        }
        return true;

    }

}

Oczekiwany wynik:

Wynik liczby pierwszej od 1 do 100 w Java program będzie:

Prime numbers from 1 to 100 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Wartość 2 jest uwzględniana, ponieważ warunek pętli wewnętrznej jest spełniony i <= 2 / 2 ocenia na 2 <= 1, co od razu jest fałszem, więc metoda zwraca wartość true bez ani jednego dzielenia.

Zoptymalizowana wersja wykorzystująca ograniczenie pierwiastka kwadratowego

Dzielenie do połowy liczby jest poprawne, ale wykonuje niepotrzebną pracę. Dzielniki zawsze występują parami wokół pierwiastka kwadratowego, więc każdy czynnik powyżej √n ma partnera poniżej, który został już sprawdzony.

public class PrimeNumbersOptimized {

    public static void main(String[] args) {
        int maxCheck = 100;
        int count = 0;
        StringBuilder result = new StringBuilder();

        for (int i = 2; i <= maxCheck; i++) {
            if (isPrime(i)) {
                result.append(i).append(" ");
                count++;
            }
        }

        System.out.println("Prime numbers from 1 to " + maxCheck + " are:");
        System.out.println(result.toString().trim());
        System.out.println("Total primes found: " + count);
    }

    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        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;
    }
}

Wyjście:

Prime numbers from 1 to 100 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Total primes found: 25

Wydrukuj Prime Numbers Korzystanie z sita Eratostenesa

Gdy potrzebna jest każda liczba pierwsza z danego zakresu, dzielenie próbne to niewłaściwe narzędzie. Sito Eratostenesa buduje tablicę boolowską, oznacza wielokrotności każdej liczby pierwszej jako złożone i odczytuje to, co pozostaje nieoznaczone.

Metoda ta działa w trzech krokach:

1. Utwórz tablicę wartości logicznych o rozmiarze n+1 i załóż, że każdy indeks od 2 w górę jest liczbą pierwszą.
2. Zaczynając od 2, oznacz każdą wielokrotność bieżącej liczby pierwszej jako liczbę złożoną.
3. Przejdź do następnego nieoznaczonego indeksu i powtarzaj, aż zostanie przekroczony pierwiastek kwadratowy z n.

import java.util.Arrays;

public class SieveOfEratosthenes {

    public static void main(String[] args) {
        int n = 100;
        boolean[] composite = new boolean[n + 1];

        for (int p = 2; p * p <= n; p++) {
            if (!composite[p]) {
                // start at p*p because smaller multiples are already marked
                for (int multiple = p * p; multiple <= n; multiple += p) {
                    composite[multiple] = true;
                }
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            if (!composite[i]) {
                result.append(i).append(" ");
            }
        }

        System.out.println("Prime numbers from 1 to " + n + " are:");
        System.out.println(result.toString().trim());
    }
}

Wyjście:

Prime numbers from 1 to 100 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Porównanie trzech podejść

Wszystkie trzy programy drukują te same 25 wartości, więc wybór zależy wyłącznie od rozmiaru zakresu.

Sprawdź nasz program, aby znaleźć liczby pierwsze z dowolnej liczby wejściowej gdy konieczne jest przetestowanie pojedynczej wartości, a nie zakresu. Aby uzyskać więcej ćwiczeń z pętlami, zapoznaj się z Ciąg Fibonacciego w JavaThe Java program palindromowyi Bubble Algorytm sortowania w Java. Tablica wartości logicznych używana przez sito jest wyjaśniona dalej w Java tablice.

FAQ