Liczby pierwsze

Zgodnie z definicją liczba pierwsza to taka, która spełnia następujący warunek:

• ma tylko dwa dzielniki: jeden i samą siebie.

Zaimplementujmy w języku C++ algorytm pozwalający sprawdzić, czy podana liczba jest liczbą pierwszą.

Zacznijmy od utworzenia dwóch zmiennych: jednej typu całkowitego (int) o nazwie liczbaTest oraz drugiej typu bool, która będzie się nazywać czyPierwsza. Do liczbaTest zostanie zapisana liczba, którą użytkownik wpisał na klawiaturze, w celu sprawdzenia, czy jest ona liczbą pierwszą. Natomiast zmienna czyPierwsza będzie przyjmować wartość true lub false w zależności od tego, czy mamy do czynienia z liczbą pierwszą, czy też nie.

Ponieważ wspomnieliśmy o interakcji programu z użytkownikiem, napiszmy kod odpowiedzialny za możliwość wprowadzenia przez użytkownika własnych danych, czyli w tym przypadku liczby, która ma zostać poddana sprawdzeniu.

int liczbaTest;
bool czyPierwsza;

cin >> liczbaTest;

Następnym krokiem będzie napisanie pętli, w której będziemy sprawdzać liczby od 2 do liczby mniejszej o jeden od podanej. Ponieważ dzielnikami liczby pierwszej jest 1 i podana liczba, więc w przedziale  nie powinno być żadnego dzielnika podanej liczby. W przypadku wykrycia dzielnika całkowitego pętla zostanie przerwana instrukcją break, a zmienna logiczna czyPierwsza przyjmie wartość false, co będzie oznaczało, że podana przez użytkownika liczba nie jest liczbą pierwszą.

for(int i = 2; i < liczbaTest; i++) {
	if(liczbaTest % i == 0) {
		czyPierwsza = false;
		break;
	}
}

for(int i = 2; i*i <= liczbaTest; i++) {
	if(liczbaTest % i == 0) {
		czyPierwsza = false;
		break;
	}
}

Na koniec określamy, jaki komunikat ma się pojawić na standardowym wyjściu, w zależności od tego, jaka jest wartość zmiennej czyPierwsza.

if(czyPierwsza == true) {
	cout << "Podana liczba jest liczbą pierwszą" << endl;
} else {
	cout << "Podana liczba nie jest liczbą pierwszą" << endl;
}

Zobaczmy kod całego programu.

#include <iostream>

using namespace std;

int main() {
	int liczbaTest;
	bool czyPierwsza = true;
    
	cout << "Podaj liczbę, którą chcesz poddać sprawdzeniu:" << endl;
	cin >> liczbaTest;
    
	for(int i = 2; i < liczbaTest; i++) {
		if(liczbaTest % i == 0) {
			czyPierwsza = false;
			break;
		}
	}

	if(czyPierwsza == true) {
		cout << "Podana liczba jest liczbą pierwszą" << endl;
	} else {
		cout << "Podana liczba nie jest liczbą pierwszą" << endl;
	}

	return 0;
}

Warto zauważyć, że w tej implementacji algorytmu wychodzimy z założenia, że podana liczba jest liczbą pierwszą, ponieważ przy deklaracji zmiennej logicznej czyPierwsza nadajemy jej wartość true. Po wykonaniu pętli for, jeżeli wartość czyPierwsza nie zostanie zmieniona, jej wartość nadal będzie wynosić true, a my uzyskamy pewność, że mamy do czynienia z liczbą pierwszą.

Liczby doskonałe

Zacznijmy od przypomnienia warunku, jaki musi spełniać liczba doskonała:

• Suma dzielników mniejszych od sprawdzanej liczby musi być równa tej liczbie.

Przykładami liczb doskonałych są:

• 6, ponieważ:

gdzie 1, 2 i 3 to dzielniki właściwedzielniki właściwedzielniki właściwe liczby 6.

• 28, ponieważ:

gdzie 1, 2, 3, 4, 7, 14 to dzielniki właściwe liczby 28.

Można zauważyć, że nasz algorytm będzie polegał na znalezieniu dzielników podanej liczby, zsumowaniu ich i sprawdzeniu, czy wynik jest równy sprawdzanej liczbie. Przeanalizujmy kod programu, który stanowi rozwiązanie tego problemu:

#include <iostream>

using namespace std;

int main() {
	int liczba;
	int sumaDzielnikow = 0;

	cout << "Podaj liczbę do sprawdzenia:" << std;
	cin >> liczba;

	for(int i = 1; i < liczba; i++) {
		if(liczba % i == 0) {
			sumaDzielnikow = sumaDzielnikow + i;
		}
	}

	if(sumaDzielnikow == liczba) {
		cout << "Dana liczba jest liczbą doskonałą";
	} else {
		cout << "Dana liczba nie jest liczbą doskonałą";
	}
}

W pętli for sprawdzamy, czy kolejne liczby (zaczynając od 1) są dzielnikami zmiennej liczbaTest. Jeżeli znajdziemy taki dzielnik, dodajemy go do zmiennej sumaDzielnikow. Następnie porównujemy wartość zmiennej sumaDzielnikow z podaną do sprawdzenia liczbą. Jeżeli są one równe, to jest to liczba doskonała.

Liczba doskonała – optymalizacja algorytmu

Zastanówmy się, czy można zoptymalizować przedstawiony wyżej algorytm. Pierwszą rzeczą, którą możemy zrobić, jest rozpoczęcie przetwarzanie pętli od liczby 2, ponieważ każda liczba jest podzielna przez 1. Unikniemy dzięki temu jednej, niepotrzebnej iteracji.

Możemy także dodać warunek wewnątrz pętli. Pozwoli to sprawdzić, czy aktualna wartość zmiennej sumaDzielnikow nie jest większa od badanej liczby. W ten sposób uda się uniknąć wykonywania wielu niepotrzebnych cykli pętli.

Niżej przedstawiamy kod programu po wprowadzeniu zmian optymalizacyjnych.

#include <iostream>

using namespace std;

int main() {
	int liczba;
	int sumaDzielnikow = 1;

	cout << "Podaj liczbę do sprawdzenia:" << endl;
	cin >> liczba;

	for(int i = 2; i < liczba; i++) {
		if(liczba % i == 0) {
			sumaDzielnikow = sumaDzielnikow + i;
            
			if(sumaDzielnikow > liczba) {
				break;
			}
		}
	}

	if(sumaDzielnikow == liczba) {
		cout << "Dana liczba jest liczba doskonałą";
	} else {
		cout << "Dana liczba nie jest liczba doskonałą";
	}
}

Liczby zaprzyjaźnione

Liczby zaprzyjaźnione to takie, których suma dzielników właściwych pierwszej liczby jest równa wartości drugiej liczby, a suma dzielników właściwych drugiej liczby jest równa wartości pierwszej liczby.

Przykładem pary takich liczb są: 220 i 284.

Dzielniki właściwe liczby 220 to: $1+2+4+5+10+11+20+$$+22+44+55+110=284$. Natomiast dzielniki właściwe liczby 284 to: $1+2+4+71+142=220$.

Przeanalizujmy implementację algorytmu, która pozwoli sprawdzić, czy podane przez użytkownika dwie liczby są zaprzyjaźnione.

#include <iostream>

using namespace std;

int main() {
	int liczba1, liczba2;
	int l1Suma = 0;
	int l2Suma = 0;
    cout << "Podaj pierwszą liczbę do sprawdzenia:" << endl;
	cin >> liczba1;
    cout << "Podaj drugą liczbę do sprawdzenia:" << endl;
	cin >> liczba2;

	for(int i = 1; i < liczba1; i++) {
		if(liczba1 % i == 0) {
			l1Suma += i;
		}
	}

	for(int i = 1; i < liczba2; i++) {
		if(liczba2 % i == 0) {
			l2Suma += i;
		}
	}

	if(liczba1 == l2Suma && liczba2 == l1Suma) {
		cout << "To są liczby zaprzyjaźnione";
	} else {
		cout << "To nie są liczby zaprzyjaźnione";
	}
}

Na początku programu deklarujemy zmienne liczba1 i liczba2. To w nich zapiszemy liczby, które użytkownik podał do sprawdzenia. Kolejne zmienne to l1Suma oraz l2Suma. Będą one odpowiadały kolejno sumie dzielników właściwych liczby pierwszej i sumie dzielników właściwych liczby drugiej.

Następnie w pętlach for sprawdzamy kolejne dzielniki liczb i sumujemy je. W końcowej części programu porównujemy wartość pierwszej liczby z sumą dzielników liczby drugiej i wartość liczby drugiej z sumą dzielników liczby pierwszej, a następnie wypisujemy odpowiedni komunikat.

Słownik