Zapis algorytmu w języku Java - P+R_W14_M03_Java Czy liczba jest liczbą pierwszą?

R78GBM2ZZ46P3

Już wiesz

Jakie własności musi posiadać liczbę, aby była liczbą pierwszą.
I rozumiesz algorytm zapisany w pseudokodzie, testujący czy dana liczba jest liczbą pierwszą.

Teraz czas, aby zapisać algorytm w postaci programu w języku Python.

Wersja I (wolniejsza, opiera się na definicji liczby pierwszej)

Linia 1. import java kropka util kropka Scanner średnik. Linia 4. public class czyPierwsza otwórz nawias klamrowy. Linia 5. prawy ukośnik prawy ukośnik Metoda sprawdza przecinek czy liczba n jest liczbą pierwszą kropka. Linia 6. static int czypierwsza otwórz nawias okrągły int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły n otwórz nawias ostrokątny 2 zamknij nawias okrągły. Linia 8. return 0 średnik prawy ukośnik prawy ukośnik liczby mniejsze od 2 nie są pierwsze. Linia 9. else. Linia 10. for otwórz nawias okrągły int i znak równości 3 średnik i otwórz nawias ostrokątny znak równości n minus 1 średnik i plus plus zamknij nawias okrągły. Linia 11. if otwórz nawias okrągły n procent i znak równości znak równości 0 zamknij nawias okrągły prawy ukośnik prawy ukośnik jeśli znajdziemy dzielnik. Linia 12. return 0 średnik. Linia 13. return 1 średnik. Linia 15. zamknij nawias klamrowy. Linia 17. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. Scanner scanner znak równości new Scanner otwórz nawias okrągły System kropka in zamknij nawias okrągły średnik. Linia 20. System kropka out kropka print otwórz nawias okrągły cudzysłów Podaj n dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 21. int n znak równości scanner kropka nextInt otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 23. if otwórz nawias okrągły czypierwsza otwórz nawias okrągły n zamknij nawias okrągły znak równości znak równości 1 zamknij nawias okrągły. Linia 24. System kropka out kropka print otwórz nawias okrągły cudzysłów Liczba jest pierwsza cudzysłów zamknij nawias okrągły średnik. Linia 25. else. Linia 26. System kropka out kropka print otwórz nawias okrągły cudzysłów Liczba nie jest pierwsza cudzysłów zamknij nawias okrągły średnik. Linia 28. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy.

import java.util.Scanner; 


public class czyPierwsza {
	//Metoda sprawdza, czy liczba n jest liczbą pierwszą.
	static int czypierwsza(int n) {
		if (n < 2)
			return 0; // liczby mniejsze od 2 nie są pierwsze
		else
			for (int i = 3; i <= n - 1; i++)
				if (n % i == 0) // jeśli znajdziemy dzielnik
					return 0;
		return 1;
		
	}

	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		System.out.print("Podaj n: ");
		int n = scanner.nextInt();
		
		if (czypierwsza(n)==1)
			System.out.print("Liczba jest pierwsza");
		else
			System.out.print("Liczba nie jest pierwsza ");

	}

}

Plik z programem do pobrania:

RU7EM92XMD1BA

Przycisk do pobrania pliku TXT z programem.

Plik JAVA o rozmiarze 668.00 B w języku polskim

Opis działania programu.

Sprawdzamy, czy liczba jest mniejsza od 2; wtedy na pewno nie jest pierwsza.
Szukamy dzielników wśród liczb naturalnych w zakresie od 2 do n‑1:

jeśli znajdziemy dzielnik, liczba nie jest pierwsza,
jeśli nie znajdziemy żadnego, to znaczy, że liczba jest pierwsza.

Ważne!

Ta metoda jest prostsza, ale wolniejsza dla dużych liczb, bo trzeba sprawdzić wszystkie możliwe dzielniki aż do n‑1.

Wersja II (szybsza, sprawdza dzielniki liczby w przedziale <2, sqrt(n)>)

Linia 1. import java kropka util kropka Scanner średnik. Linia 4. public class czyPierwsza otwórz nawias klamrowy. Linia 5. prawy ukośnik prawy ukośnik Metoda sprawdza przecinek czy liczba n jest liczbą pierwszą kropka. Linia 6. static int czypierwsza otwórz nawias okrągły int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. int p znak równości otwórz nawias okrągły int zamknij nawias okrągły Math kropka sqrt otwórz nawias okrągły n zamknij nawias okrągły średnik. Linia 8. if otwórz nawias okrągły n otwórz nawias ostrokątny 2 zamknij nawias okrągły. Linia 9. return 0 średnik prawy ukośnik prawy ukośnik liczby mniejsze od 2 nie są pierwsze. Linia 10. else. Linia 11. for otwórz nawias okrągły int i znak równości 3 średnik i otwórz nawias ostrokątny znak równości p średnik i plus plus zamknij nawias okrągły. Linia 12. if otwórz nawias okrągły n procent i znak równości znak równości 0 zamknij nawias okrągły prawy ukośnik prawy ukośnik jeśli znajdziemy dzielnik. Linia 13. return 0 średnik. Linia 14. return 1 średnik. Linia 16. zamknij nawias klamrowy. Linia 18. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. Scanner scanner znak równości new Scanner otwórz nawias okrągły System kropka in zamknij nawias okrągły średnik. Linia 21. System kropka out kropka print otwórz nawias okrągły cudzysłów Podaj n dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 22. int n znak równości scanner kropka nextInt otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 24. if otwórz nawias okrągły czypierwsza otwórz nawias okrągły n zamknij nawias okrągły znak równości znak równości 1 zamknij nawias okrągły. Linia 25. System kropka out kropka print otwórz nawias okrągły cudzysłów Liczba jest pierwsza cudzysłów zamknij nawias okrągły średnik. Linia 26. else. Linia 27. System kropka out kropka print otwórz nawias okrągły cudzysłów Liczba nie jest pierwsza cudzysłów zamknij nawias okrągły średnik. Linia 29. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy.

import java.util.Scanner; 


public class czyPierwsza {
	//Metoda sprawdza, czy liczba n jest liczbą pierwszą.
	static int czypierwsza(int n) {
    	int p = (int) Math.sqrt(n);
		if (n < 2)
			return 0; // liczby mniejsze od 2 nie są pierwsze
		else
			for (int i = 3; i <= p; i++)
				if (n % i == 0) // jeśli znajdziemy dzielnik
					return 0;
		return 1;
		
	}

	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		System.out.print("Podaj n: ");
		int n = scanner.nextInt();
		
		if (czypierwsza(n)==1)
			System.out.print("Liczba jest pierwsza");
		else
			System.out.print("Liczba nie jest pierwsza ");

	}

}

Plik z programem do pobrania:

RVSDDP6GP5X2B

Przycisk do pobrania pliku TXT z programem.

Plik JAVA o rozmiarze 700.00 B w języku polskim

Opis działania programu:

Sprawdzamy wyjątki: liczby mniejsze od 2 nie są pierwsze, a 2 jest jedyną parzystą liczbą pierwszą.
Odrzucamy parzyste – jeśli liczba > 2 i jest parzysta, od razu zwracamy False.
Sprawdzamy tylko do √n – przyspiesza działanie, bo nie musimy badać wszystkich dzielników.
Iterujemy tylko po nieparzystych (3, 5, 7, …).

Liczby i ich tajemnice

Dla zainteresowanych: Liczby bliźniacze