Sprawdzanie czy liczba jest liczbą pierwszą

Sprawdzanie czy liczba jest liczbą pierwszą
IG
  • Rejestracja:prawie 3 lata
  • Ostatnio:prawie 2 lata
  • Postów:27
0

Cześć,
ostatnio mój znajomy na rozmowie kwalifikacyjnej musiał napisać program, który definiuje czy dana liczba jest liczbą pierwszą:
Mam dwie wersje programu:
1)

Kopiuj
while True:
    a = int(input("Podaj liczbę: "))
    for i in range(2,a):
        if a % i == 0:
            print("not prime")
            break
        else:
            print("prime")
            break

W tym wypadku np. liczbę "9" oraz liczbę "25 zalicza jako liczbę pierwszą". Dlaczego? Gdzie leży błąd i czemu jest to źle rozwiązane?

Dlaczego np. w tym wypadku program działa poprawnie?

Kopiuj
while True:
    a = int(input("Podaj liczbę: "))
    for i in range(2,a):
        if a % i == 0:
            print("not prime")
            break
    else:
        print("prime")

Może ktoś ma dostęp do strony/materiałów, które mogłyby wyjaśnić problem?

edytowany 2x, ostatnio: Riddle
Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
5

W tym wypadku np. liczbę "9" oraz liczbę "25 zalicza jako liczbę pierwszą".

Przerywasz pętlę już po pierwszym warunku, a zatem Twój program jedynie sprawdza czy podana liczba jest podzielna przez dwa, podczas gdy powinien sprawdzać podzielność od 2 do a (albo, trochę lepiej, do ceil(sqrt(a))) i dopiero na podstawie tego wysuwać wniosek.


edytowany 2x, ostatnio: Patryk27
IG
No ok, to dlaczego w takim razie przesunięcie "else" na równi z "for" pozwala sprawdzić pozostałe dzielniki? Tam przecież też jest "break".
_13th_Dragon
@Patryk27: Pobudka! Przez 1 dzieli się każda. :D
Althorion
Moderator C/C++
  • Rejestracja:prawie 10 lat
  • Ostatnio:około 2 godziny
  • Postów:1603
4

Na przyszłość — weź debugger do ręki i sprawdź. Po to to narzędzie istnieje…

A co do meritum — zauważ, że pierwszy kod wypisze prime i przerwie pętlę jak tylko if nie będzie prawdziwy. Raz. W szczególności, przy pierwszej iteracji — u Ciebie każda liczba nieparzysta będzie pierwsza.

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
3

No ok, to dlaczego w takim razie przesunięcie "else" na równi z "for" pozwala sprawdzić pozostałe dzielniki? Tam przecież też jest "break".

Jest break, ale dopiero gdy program znajdzie dowód na to, że liczba jest złożona -- taki break stanowi wtedy optymalizację, bo znalazłszy jeden dzielnik (poza 1 i liczbą wejściową, wiadomo) nie trzeba patrzeć na resztę: wiadomo, że liczba pierwszą nie jest.

To znaczy:

  • wiadomo, że 24 nie jest liczbą pierwszą, bo dzieli się przez 2 (i nie trzeba dalej udowadniać, że jeszcze dzieli się np. przez 12),
  • wiadomo, że 25 nie jest liczbą pierwszą, bo choć nie dzieli się ani przez 2, ani przez 3, to dzieli się przez 5,
  • wiadomo, że 47 jest liczbą pierwszą, bo nie dzieli się ani przez 2, ani przez 3, ani przez 5, ani /* ... */.

Inną, mniej optymalną wersją tego algorytmu mogłoby być:

Kopiuj
a = int(input("Podaj liczbę: "))

czy_pierwsza = True

for i in range(2, a):
    czy_pierwsza = czy_pierwsza and (a % i != 0)

if czy_pierwsza:
    print("prime")
else:
    print("not prime")

(a ten algorytm jest mniej optymalny właśnie dlatego, że znalazłszy już jeden dowód na niepodzielność - np. 2 w przypadku 24 - i tak sprawdza dalej 24 % 3, 24 % 4, 24 % 5 itd.)


edytowany 7x, ostatnio: Patryk27
ZD
  • Rejestracja:około 3 lata
  • Ostatnio:ponad rok
  • Postów:2310
0
Ignacy napisał(a):

Cześć,
ostatnio mój znajomy na rozmowie kwalifikacyjnej musiał napisać program, który definiuje czy dana liczba jest liczbą pierwszą:

To powiedz ":znajomemu", że ciężko będzie, jak to zadanie ejst jakimkolwiek problemem

(z innego wątku)

Ignacy napisał(a):

Cześć wszystkim,
Od kilku miesięcy ucze sie regularnie Pythona, mam jednak pewien problem, którym staram się nie przejmować a regularnie podcina mi skrzydła.
Mianowicie.. Bardzo często spotykam się z opinią, że obecnie jest ogrom osób chcących dostać pracę jako Junior Python Developer a pracy dla juniorów jest stosunkowo niedużo.
Myślicie, że dalej jest możliwość, aby dostać się do pracy bez studiów kierunkowych czy raczej studentów jest juz tak dużo, że tylko oni będą brani pod uwagę?

  • kolejna kwestia. Waszym zdaniem dobrym pomysłem jest kontynuowanie nauki Pythona czy na start łatwiej byłoby dostać pracę np. w PHP albo .NET?

Tak ja ci odpowiedziano w tamtym wątku - rzeczywiste kwalifikacje a chciejstwo, ani nawet kwity


If you put a million monkeys at a million keyboards, one of them will eventually write a Java program - the rest of them will write Perl
IG
  • Rejestracja:prawie 3 lata
  • Ostatnio:prawie 2 lata
  • Postów:27
0
ZrobieDobrze napisał(a):
Ignacy napisał(a):

Cześć,
ostatnio mój znajomy na rozmowie kwalifikacyjnej musiał napisać program, który definiuje czy dana liczba jest liczbą pierwszą:

To powiedz ":znajomemu", że ciężko będzie, jak to zadanie ejst jakimkolwiek problemem

(z innego wątku)

Ignacy napisał(a):

Cześć wszystkim,
Od kilku miesięcy ucze sie regularnie Pythona, mam jednak pewien problem, którym staram się nie przejmować a regularnie podcina mi skrzydła.
Mianowicie.. Bardzo często spotykam się z opinią, że obecnie jest ogrom osób chcących dostać pracę jako Junior Python Developer a pracy dla juniorów jest stosunkowo niedużo.
Myślicie, że dalej jest możliwość, aby dostać się do pracy bez studiów kierunkowych czy raczej studentów jest juz tak dużo, że tylko oni będą brani pod uwagę?

  • kolejna kwestia. Waszym zdaniem dobrym pomysłem jest kontynuowanie nauki Pythona czy na start łatwiej byłoby dostać pracę np. w PHP albo .NET?

Tak ja ci odpowiedziano w tamtym wątku - rzeczywiste kwalifikacje a chciejstwo, ani nawet kwity

Nie wiem po co ta uszczypliwość.
I tak, to zadanie otrzymał mój znajomy na rozmowie na Juniora. Dostał też parę innych zadań, które próbowałem rozwiązać - część z powodzeniem.
Chyba od tego jest to forum, aby sobie pomagać i się wzajemnie wspierać. Jeśli zaglądasz tutaj, aby tylko marudzić - lepiej usiądź wygodnie w fotelu i napij się herbaty.

_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:3 miesiące
0
Ignacy napisał(a):

Nie wiem po co ta uszczypliwość.
I tak, to zadanie otrzymał mój znajomy na rozmowie na Juniora. Dostał też parę innych zadań, które próbowałem rozwiązać - część z powodzeniem.
Chyba od tego jest to forum, aby sobie pomagać i się wzajemnie wspierać. Jeśli zaglądasz tutaj, aby tylko marudzić - lepiej usiądź wygodnie w fotelu i napij się herbaty.

Owszem to forum aby pomagać tylko nie sobie zaś tym co naprawdę chcą się nauczyć a nie udają że chcą.
Jak ktoś prosi o pomoc z problemem do zrozumienia którego wystarczy byle kurs z google przy czym pierwsze kilka stron to albo to zwykły troll albo nigdy nie nauczy się niczego z programowania, ponieważ jedną z podstawowych umiejętności dla programisty jest umiejętność znalezienia informacji w sieci lub w "słabej" dokumentacji.
Więc skoro to troll lub osoba nie nadająca się to większość zwyczajnie nie chce marnować na to czasu, a skoro już wymusiłeś tą stratę czasu (bo musiał przeczytać) to uszczypliwość wg mnie jest całkowicie zasadna.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
ZD
Zadanie jest na poziomie 2-3mc nauki pythona, a nie rozmowy kwalifikacyjnej. Więc i tak tam ulgowo było. BTW śliczny temat na elementarz, ale taki najbardziej bazowy algorytmiki. Najbardziej szkolna wersji liczb pierwszych -> odstrzał. Wasze starty w tych rekrutacjach to marnowanie czasu człowiekowi technicznemu do tej rekrutacji
IG
było też zadanie: Zsumuj liczby znajdujące się w liście: lista = ["sdfjsdj21asfkf34ksfkf45"] efekt końcowy ma wynosic: 21 + 34 + 45 = 100. Trzeba było to zrobić iteracyjnie a nie za pomocą regexów.
_13th_Dragon
Nadal podstawy podstaw, czyli byle kurs z googla.
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)