Sprawdzanie czy liczba jest liczbą pierwszą

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)

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?

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?

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.

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.

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ć:

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.)

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

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.

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.