Algorytm sprawdzenia liczby pierwszej

Chciałbym za pomocą prostego algorytmu sprawdzać czy dana liczba jest pierwsza. Na razie zaimplementowałem żeby sprawdzał czy dana liczba jest większa od 1

Czego jeszcze bym potrzebował, żeby to rozwiązać?

No sprawdzenie czy liczba jest pierwszą to trochę trudny problem, są szybkie algorytmy, ale najprostszy to sito erastotenesa.

Ale przez to, że prosty to nie jest najszybszy.

Ten problem sprawia, że bardzo trudno jest złamać algorytmy szyfrowania typu RSA, z powodu właśnie trudności obliczania tych liczb pierwszych i ich rozkładu bo zwykle mnoży się dwie liczby pierwsze i później trzeba znaleźć dwie takie, które dają taki wynik, a że wszystkie obliczenia są skomplikowane to dużo czasu to zajmuje.

Ten "schemat" nawet nie ma sensu, przy decyzji powinny być dwa wyjścia i jedno wejście. Czy ty to naszkicowałeś w 10 sekund żeby wyglądało że coś zrobiłeś i łatwiej wyprosić gotowca?
Rejestracja: około 6 lat :o

zadanie ze studiów od prowadzącego: "Sprawdzić czy liczba jest pierwsza."

@piotrek1998: Masz napisać algorytm, czy schemat blokowy?
Tak czy siak, polecam szukać: "primality test".

Nie dziekuj, bo nie ma za co - studia mają zmusić do myślenia i samodzielności. Szukanie odpowiedzi na trywialne pytania (trywialne nie w sensie czasochłonności, ale sam byś do tego doszedł jakbyś nie szukał pomocy od razu) to nie jest samodzielność.

W ogole jeszcze nikt nie narzekał, że schematy blokowe są bez sensu, niepraktyczne, a na studiach powinni uczyć praktycznych rzeczy, jakiejś Javy czy Reacta. Dziwne.

Właśnie miałem napisać, że schematy blokowe są bez sensu :P, chociaż z tym Reactem i Javą to już przesada.

Blokowe nie są jakoś szczególnie przydatne, pseudokod jednak wygrywa zwiezloscią, ale jak kogoś przerasta przepisanie algo do schematu to problem nie leży w schematach.

lion137 napisał(a):

Włąśnie miałem napisać, żę schematy blokowe są bez sensu :P, chociaż z tym Reactem i Javą to już przesada.

To jest przecież tylko forma - treść się liczy.

tumor napisał(a):

No sprawdzenie czy liczba jest pierwszą to trochę trudny problem, są szybkie algorytmy, ale najprostszy to sito erastotenesa.

Ale przez to, że prosty to nie jest najszybszy.

Ten problem sprawia, że bardzo trudno jest złamać algorytmy szyfrowania typu RSA, z powodu właśnie trudności obliczania tych liczb pierwszych i ich rozkładu bo zwykle mnoży się dwie liczby pierwsze i później trzeba znaleźć dwie takie, które dają taki wynik, a że wszystkie obliczenia są skomplikowane to dużo czasu to zajmuje.

Moim zdaniem nie ma potrzeby tutaj się wysilać i tworzyć jakieś eleganckie rozwiązania.

Student ma sprawdzić, czy liczba jest pierwsza.
Niech algorytm brutalnie w pętli sprawdzi wszystkie dzielenia liczby N przez liczby z przedziału od 2 do N-1.

Ewentualnie można zmniejszyć ilość iteracji o połowę, bo liczby większe niż połowa N na pewno nie dzielą liczby N.

piotrek1998 napisał(a):

Czego jeszcze bym potrzebował, żeby to rozwiązać?

Z historii postów pozornie by wynikało, że masz podstawy oblatania w IT.
Ilość i jakość wkładu własnej pracy zaprezentowałeś jak plącząca nad zadaniem blondynka

Do tej pory kupowałeś zaliczenia ?

@piotrek1998: Przejrzałem nieco twoje konto i wynika z niego że już dobre parę lat zabierasz się za naukę programowania. Próbowałeś Javascriptu, PHP, C++, ale za każdym razem od tych paru lat zdaje się, że grzęźniesz w podstawach. Raz pytałeś wręcz jak nauczyć się myślenia logicznego - i odnoszę wrażenie, że ci go niestety brakuje, a ono jest moim zdaniem kluczowe w programowaniu.

Nie mówię tego żeby cię obrazić ani ci dopiec - nie ma w tym nic wstydliwego, różnych zajęć na świecie jest masa i programowanie nie jest dla każdego odpowiednie.

Jeśli tyle lat dalej masz problemy z podstawami, to to naprawdę jest to znak do zastanowienia się, czy nie lepiej spróbować swoich sił w czymś innym.

Jak nie rozumiesz czegoś na studiach, to po prostu pytaj wykładowców, poproś żeby Ci wytłumaczyli. Generalnie skoro Cię tam przyjęli, to biorą za to pieniądze, żeby Cię czegoś nauczyć. Tylko studenci niepotrzebnie wstydzą się zadawać pytania - a nie ma głupich pytań. Nikt od razu wszyskiego nie wie.

Spine napisał(a):

Niech algorytm brutalnie w pętli sprawdzi wszystkie dzielenia liczby N przez liczby z przedziału od 2 do N-1.

Ewentualnie można zmniejszyć ilość iteracji o połowę, bo liczby większe niż połowa N na pewno nie dzielą liczby N.

Można też być hardkorem i sprawdzać dzielniki do sqrt(N), bo coś mi mówi, że dalej sprawdzać nie trzeba.
A w ogóle to można najpierw sprawdzić dzielność przez 2 i 3, a potem zacząć od 5 z krokiem co 6.

@somekind: dobrze by było, żeby chociaż najkrótszy sposób sam zaimplementował. Potem można to ulepszać ;)

dalbajob napisał(a):

@piotrek1998: Przejrzałem nieco twoje konto i wynika z niego że już dobre parę lat zabierasz się za naukę programowania. Próbowałeś Javascriptu, PHP, C++, ale za każdym razem od tych paru lat zdaje się, że grzęźniesz w podstawach. Raz pytałeś wręcz jak nauczyć się myślenia logicznego - i odnoszę wrażenie, że ci go niestety brakuje, a ono jest moim zdaniem kluczowe w programowaniu.

Nie mówię tego żeby cię obrazić ani ci dopiec - nie ma w tym nic wstydliwego, różnych zajęć na świecie jest masa i programowanie nie jest dla każdego odpowiednie.

Jeśli tyle lat dalej masz problemy z podstawami, to to naprawdę jest to znak do zastanowienia się, czy nie lepiej spróbować swoich sił w czymś innym.

Popieram

Dodam, uczyć sie podstaw, istnienia i sensu "if" na studiach to można było w latach 1980ch, początku 1990
Dziś to poziom ucznia 7 klasy podstawówki - jeśli ma ku temu tzw predyspozycje. Nie mówię o szczególnie utalentowanych, bo oni w piątej klasie, ale o solidnym średnim

Nie patrz na gotowce, problem jest latwy i można samemu wymyślić algorytm. Poczytaj/posłuchaj u Matemaksa co trzeba spełnić, aby liczba byla liczba pierwsza i potem to sprawdź kodem.

Jakby interesowały Cię wszystkie liczby pierwsze z określonego zakresu to wtedy najlepiej skorzystać z algorytmu sita Erastotenesa, ale co do dokładnego sprawdzenie pierwszości pojedynczej liczby ciężko wymyślić coś ponad sprawdzanie jej podzielności przez wszystkie liczby mniejsze lub równe jej pierwiastkowi. Można by sprawdzać podzielność tylko przez liczby pierwsze i to by wystarczyło, na tym właśnie opiera się sito Erastotenesa, ale dla sprawdzenia jednej liczby nie opłaca się szukać liczb pierwszych żeby dzielić tylko przez nie. Do tego są jeszcze różne algorytmy przybliżonych testów pierwszości, które są szybsze i poprawne dla większości przypadków, ale nie dla wszystkich.

co do dokładnego sprawdzenie pierwszości pojedynczej liczby ciężko wymyślić coś ponad sprawdzanie jej podzielności przez wszystkie liczby mniejsze lub równe jej pierwiastkowi.

Możesz to jeszcze trochę zoptymalizować, np z miejsca wykluczyć liczby parzyste, podzielne przez 5, 3 itd bo wtedy już wiadomo że liczba nie jest pierwsza.