

[C++] Liczba pierwsza
Rozpoczęty przez
Eyetooth
, 23 10 2009 09:07
2 odpowiedzi w tym temacie
#1
Napisano 23 10 2009 - 09:07
Witam potrzebuje miec napisany program sprawdzajacy czy liczba jest liczba pierwsza i nie wiem jak to ma wygladac. POMOCY!

#2
Napisano 23 10 2009 - 10:44
najprosciej (czyli metoda brute-force)
dla liczby X sprawdzasz czy jest podzielna przez X-1, X-2, ..., 2
jesli ktoras z tych licbz po drodze dzieli X bez reszty to znaczy ze nie jest liczba pierwsza
oczywiscie pominac trzeba w tym wypadku liczby 1 i 2, ktore waidomo sa liczbami pierwszymi..
ale to mozna bylo wywnioskowac z definiji liczby pierwszej...
edit:
zakres dzielnikow mozna zmniejszyc do [X/2,2] (X/2 - dzielenie calkowite)
dla liczby X sprawdzasz czy jest podzielna przez X-1, X-2, ..., 2
jesli ktoras z tych licbz po drodze dzieli X bez reszty to znaczy ze nie jest liczba pierwsza
oczywiscie pominac trzeba w tym wypadku liczby 1 i 2, ktore waidomo sa liczbami pierwszymi..
ale to mozna bylo wywnioskowac z definiji liczby pierwszej...
edit:
zakres dzielnikow mozna zmniejszyc do [X/2,2] (X/2 - dzielenie calkowite)
#3
Napisano 26 10 2009 - 00:26
Chyba lepiej skorzystać z sita Eratostenesa.
Jak to działa - google Ci pomoże.
Jak to działa - google Ci pomoże.
Użytkownicy przeglądający ten temat: 0
0 użytkowników, 0 gości, 0 anonimowych