• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Jak sprawdzić czy dana liczba jest liczbą pierwszą?

Aruba Cloud VPS - 50% taniej przez 3 miesiące!
+6 głosów
55,034 wizyt
pytanie zadane 12 kwietnia 2015 w C i C++ przez Kornel Howil Początkujący (260 p.)

Stworzyłem kod (poniżej) do sprawdzenia czy dana liczba jest pierwsza jednak program nie działa poprawnie. Byłbym wdzięczny za wskazanie błędu i pomoc.

#include <iostream>

using namespace std;

int test, liczba;

int main()
{
    cin >> test;

    for(int i=0; i<test; i++)
    {
        cin >> liczba;

        int x=2;

        while(x<liczba)
        {
            if(liczba%x==0)
            {
                if(liczba==x)
                    cout << "Tak";
                else
                    cout << "Nie";
            }
            else
            {
                x++;
            }
        }
    }
    return 0;
}

 

6 odpowiedzi

+2 głosów
odpowiedź 12 kwietnia 2015 przez marqos12 Obywatel (1,840 p.)
wybrane 12 kwietnia 2015 przez Kornel Howil
 
Najlepsza
#include <iostream>

using namespace std;

int test, liczba;

int main()
{
    cin >> test;

    for(int i=0; i<test; i++)
    {
        cin >> liczba;
        for (int i=2; i<=liczba; i++){
            if (liczba%i==0){
                if (i==liczba) cout<<"TAK"<<endl
                else cout<<"NIE"<<endl;
                break;
            }

        }

     
    }
    return 0;
}

Niewiem dla czego, ale w takich przypadkach pętla for jest dla mnie bardziej przejrzysta. U Ciebie błąd był w warunku pętli oraz w tym, że gdy liczba nie była liczba pierwszą, np: 12 to wyświetlało NIE kilkukrotnie.

komentarz 18 grudnia 2017 przez sabah Nowicjusz (100 p.)
a nie obeszloby sie bez tej zewnetrznej petli?
komentarz 1 lipca 2018 przez LD Nowicjusz (100 p.)
if (i==liczba) cout<<"TAK"<<endl     // na końcu tej linii chyba powinien być średnik
+2 głosów
odpowiedź 12 kwietnia 2015 przez krecik1334 Maniak (58,390 p.)
Szukaj dzielników tylko do pierwiastka z liczby sprawdzanej. Taki jest przepis na sukces.
komentarz 12 kwietnia 2015 przez Berike Początkujący (420 p.)
można tez zrobić zamiast pierwiastka w pętli for i <= (liczba/2)
komentarz 12 kwietnia 2015 przez krecik1334 Maniak (58,390 p.)
Wolniejsze będzie, dla każdej liczby większej od 4 pierwiastek zwraca mniejszą wartość niż jej dzielenie przez 2, a więc więcej elementów do sprawdzenia.
komentarz 6 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)
ale skoro mamy użyć pierwiastka, to jego wartość trzeba zrzutować na int -zeby dzialala petla
+1 głos
odpowiedź 12 kwietnia 2015 przez bossik21 Mądrala (5,750 p.)
edycja 12 kwietnia 2015 przez bossik21

Kompilując w głowie do chodzę do wniosku, ze chyba nic Ci nie wypisuje...dlaczego? Daj warunek while-a :

while(x<=liczba)

i to

else
{
    x++;
}

zamień

x++;

 

 

ok bo jeszcze jeden błąd znalazłem. łap  teraz :

#include <iostream>
 
using namespace std;
 
int test, liczba;
 
int main()
{
    cin >> test;
 
    for(int i=0; i<test; i++)
    {
        cin >> liczba;
 
        int x=2;
 
        while(x<=liczba)
        {
            if(liczba%x==0)
            {
                if(liczba==x)
                    cout << "Tak";
                else
                {
                    cout << "Nie";
                    break;
                }
			}
                x++;
 
        }
    }
    return 0;
}

Ogólnie można by ten algorytm zoptymalizować chociażby o niesprawdzanie zakażdym razem wielokrotności 2ki.

+1 głos
odpowiedź 12 kwietnia 2015 przez daan Pasjonat (17,640 p.)

Jeżeli liczba jest < 2 to odrazu wypisz ze nie jest pierwsza, jezeli jest  >= 2 to wtedy robisz pętle 

for(int i = 2; i * i <= n; ++i) if(n % i == 0) {nie jest pierwsza konczymy sprawdzanie}

Jeżeli sprawdzi całość i nie znajdzie dzielnika to znaczy ze jest pierwsza ;)

 

+1 głos
odpowiedź 12 kwietnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)

Pamietam ze kiedy to robilem.
Zarzucilem warunek i działał - odnosząć się do Twojego kodowania

if ((liczba%2!=0)&&(liczba%3!=0)&&(liczba%5!=0))   -  wystarczył :D

+1 głos
odpowiedź 6 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)
Za dużo kombinowania :D
Tak na logikę, jeżeli liczba nie dzieli się przez 2,3 i 5 - to jest to liczba pierwsza, więc wystarczy zrobić 1 if'a, bo przy tej pętli, będzie masakra, jak ktoś walnie dużą liczbę :D
komentarz 6 sierpnia 2015 przez abuc Nowicjusz (100 p.)
edycja 6 sierpnia 2015 przez abuc
Co w takim razie z liczba 49 lub np. 169 lub jeszcze inna bedaca iloczynem dwoch jednakowych liczb pierwszych? :) Edit: gdyby Twoje rozwiazanie bylo dobre juz teraz mialbys zagwarantowanego Nobla i highlife do konca zycia. Liczby pierwsze nie sa takie proste jakby sie to moglo wydawac
komentarz 6 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)
edycja 6 sierpnia 2015 przez Dragonet.17
No racja, dzięki za uświadomienie :P
Nie przemyślałem do końca :D
Fajnie, że to nie jest takie proste, bo jest nad czym pomyśleć :P

Podobne pytania

+1 głos
2 odpowiedzi 1,757 wizyt
0 głosów
1 odpowiedź 6,806 wizyt
0 głosów
2 odpowiedzi 1,326 wizyt

93,096 zapytań

142,059 odpowiedzi

321,510 komentarzy

62,439 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...