Liczby pierwsze

Algorytm do pierwiastka:

Polega na sprawdzeniu czy liczba jest pierwsza poprzez sprawdzenie jej dzielników.

Jest on łatwy w implementacji (w zapisie), ale niestety mało wydajny (niekorzystny) przy dużej ilości liczb. Napiszmy go w postaci funkcji:

#include <iostream>
using namespace std;
bool isPrimeNumber (int n) 	//nazywamy naszą funkcję „czy liczba pierwsza”
{
	if (n<2)
		return false;
	for(int x=2;x*x<=n ;x++) 
	//zaczynamy od 2, ponieważ każda liczba dzieli się przez 1 lepiej 
	//nie używać sqrt, ponieważ może on sprawiać problemy w dalszej części 
    //programu
    // x*x<=n jest to sprawdzenie aż do pierwiastka z danej liczby, usprawnia 
    //to nasz program, ponieważ każda z liczb ma tyle samo dzielników 
    //przed i po swoim pierwiastku. Przeanalizujmy to na przykładzie:
    //dla 36 i 37
    //36: 1,2,3,4,6,9,12,18,36  (4,4)
    //38:1,2,19,38     (2,2)
    //pierwiastkiem z 36 jest 6, a z 38 pomiędzy 6,a 7
    //można zauważyć więc, że po pierwiastku z danej liczby dzielniki 
    //odpowiadają zasadzie, że liczba przez dzielnik = jeden z poprzednich 
    //dzielników np. 38/19 = 2.
	if(n%x==0)
	{			
		return false;
		//jeżeli liczba ma jakikolwiek dzielnik inny niż 1 i ona sama, 
		//oznacza to, że nie jest ona liczbą pierwszą.
	}
    return true;
    //jeżeli nie znaleźliśmy żadnego dzielnika, znaczy to, że mamy 
    //do czynienia z liczbą pierwszą
}
int main()
{
    int n;  //podajemy liczbę, którą chcemy sprawdzić
    cin>>n;
    cout<<isPrimeNumber(n); //wywołujemy naszą funkcję dla tej liczby
}

Złożoność wynosi O(pierwiastka z n), ponieważ mamy pętlę do pierwiastka.

ZADANIE: korzystając z powyższej funkcji napisz program, który wypisze, te z liczb podanych przez użytkownika, które nie są liczbami pierwszymi.

Sito Eratostenesa:

Algorytm polega na stworzeniu tablicy, która mówi czy dana liczba jest pierwsza czy nie (za pomocą 0 i 1). Wiemy to na podstawie wielokrotności pozostałych liczb pierwszych. Jest on nieprzyjemny w implementacji, jednak bardziej wydajny przy większej ilości liczb. Wadą jest również fakt, że chcąc poznać czy dana liczba jest pierwsza musimy wiedzieć to również o wszystkich ją poprzedzających.

0-liczba pierwsza, 1-liczba nie pierwsza

#include <iostream>
using namespace std;
bool tab[1000]; 
//tworzymy tablicę liczb złożoną z  zer i jedynek początkowo 
//wypełnioną samymi zerami o dowolnej wielkości
void sieveOfErasthotenes()	
{			
	tab[0]=1;			//ustawiamy 0 i 1 jako jedynki, ponieważ nie są 
	tab[1]=1;			//liczbami pierwszymi
	for(int i=2;i*i<1000;i++)		//podobnie jak w przypadku poprzedniego 
	                                //algorytmu zaczynamy od 2 i szukamy 
	                                //wielokrotności aż do pierwiastka
	{
		if(tab[i]==0)	//jeżeli znajdziemy liczbę, która jest oznaczona 	
		                //jako pierwsza
		{
			for(int j=i+i;j<1000;j+=i)	// wtedy wszystkie jej wielokrotności 
			                            //oznaczamy jako liczby nie pierwsze
				tab[j]=1;
		}
	}
}

int main()
{
    int n;
    cin>>n; //podajemy liczbę którą chcemy sprawdzić 
    sieveOfErasthotenes();
    cout<<tab[n]; 
}

Liczby pierwsze

Algorytm do pierwiastka:

Sito Eratostenesa:

Uzupłenione sito Eratostenesa:

Polityka prywatności

Regulamin korzystania ze strony

Odwiedź nasze social media!

Skontaktuj się z nami