Perfect Number Program w Pythonie: Jak sprawdzić, czy liczba jest idealna, czy nie?
Opublikowany: 2021-01-29Wstęp
Mówi się, że liczba jest liczbą doskonałą, jeśli suma jej właściwych dzielników (nie licząc samej liczby) jest równa liczbie.
Aby uzyskać lepszy pomysł, rozważmy przykład, właściwe dzielniki 6 to 1, 2, 3. Teraz suma tych dzielników jest równa 6 (1+2+3=6), więc 6 mówi się, że jest liczbą doskonałą . Podczas gdy jeśli weźmiemy pod uwagę inną liczbę, taką jak 12, właściwymi dzielnikami 12 są 1, 2, 3, 4, 6. Teraz suma tych dzielników nie jest równa 12, więc 12 nie jest liczbą doskonałą.
Programowanie w Pythonie jest stosunkowo prostsze i przyjemniejsze w porównaniu z innymi językami ze względu na prostszą składnię i dobrą czytelność. Teraz, gdy mamy jasność co do koncepcji liczby doskonałej, napiszmy program w Pythonie, aby sprawdzić, czy liczba jest liczbą idealną, czy nie. Zbudujmy kod w pythonie, aby sprawdzić, czy dane dane wejściowe użytkownika są idealną liczbą, czy nie i poznajmy zabawę z kodowaniem w pythonie. Zapoznaj się z naszymi programami analizy danych, jeśli chcesz zdobyć wiedzę specjalistyczną.
Przeczytaj: Programy wzorców Pythona
Spis treści
Program w Pythonie
Podstawowym rozwiązaniem do znalezienia idealnej liczby jest zapętlenie 2 do liczby 1, zachowanie sumy jej właściwych dzielników i sprawdzenie, czy suma jest równa liczbie.
| n=int(input("wprowadź liczbę")) suma=1 dla i w zakresie (2,n): jeśli(n%i==0): suma=suma+i jeśli(suma==n): print(n”jest liczbą idealną”) w przeciwnym razie: print(n”nie jest liczbą idealną”) |
Przejdźmy przez kod.
Najpierw inicjujemy n danymi wejściowymi użytkownika i rzutujemy je na liczbę całkowitą, ponieważ domyślnie dane wejściowe użytkownika są odczytywane jako ciąg znaków w Pythonie. Musimy sprawdzić, czy n jest liczbą doskonałą, czy nie. Zauważ, że inicjujemy sumę 1, ponieważ 1 jest właściwym dzielnikiem dla wszystkich liczb całkowitych (z wyłączeniem zera), więc możemy wykluczyć iterację w pętli i zacząć bezpośrednio od 2.
Zapętlamy 2 do liczby-1 i dodajemy liczby całkowite do sumy, jeśli jest to właściwy dzielnik. I wreszcie, kiedy wychodzimy z pętli, sprawdzamy, czy otrzymana suma jest równa liczbie, czy nie. Bułka z masłem, prawda?
Mało zoptymalizowana wersja
Po przetestowaniu powyższego programu możemy mieć pytanie, czy możemy go zoptymalizować? No ale możemy zredukować liczbę iteracji do liczby/2 bez zmiany algorytmu. Ponieważ wpadliśmy na pomysł, że liczba nie może mieć właściwego dzielnika większego niż liczba/2.
| n=int(input("wprowadź liczbę")) suma=1 dla i w zakresie (2,n//2+1): jeśli(n%i==0): suma=suma+i jeśli(suma==n): print(n”jest liczbą idealną”) w przeciwnym razie: print(n, „nie jest liczbą idealną”) |
Powyższy fragment jest prawie podobny do poprzedniego, z jedyną różnicą w pętli do number/2. Zauważ, że wykonujemy dzielenie liczb całkowitych, aby uniknąć konwersji na typ zmiennoprzecinkowy, i zapętlamy do n//2+1, ponieważ ostatnia liczba całkowita w zakresie nie jest uwzględniana w pętli Pythona.
Ograniczenia
Gdy zostaniemy poproszeni o znalezienie idealnych liczb w danym zakresie, nasze rozwiązanie zużyje czas proporcjonalnie do liczby^2, czyli złożoności czasowej O(n²). Ponieważ musimy zapętlić każdą liczbę w podanym zakresie, a następnie sprawdzić, czy dla każdej liczby są prawidłowe dzielniki. A kilka liczb spełnia warunek liczby doskonałej. Na przykład liczba idealnych liczb w zakresie od 0 do 1000 to tylko 3 (6, 28, 496).
Istnieje zoptymalizowane rozwiązanie tego problemu, w którym nie potrzebujemy pętli po wszystkich elementach, aby znaleźć odpowiednie dzielniki, wzór Euklidesa mówi, że 2 n -1(2 n -1) jest liczbą parzystą idealną, gdzie oba n, (2 n -1) jest liczby pierwsze. Na przykład 6 spełnia powyższe równanie, gdzie n wynosi 2, a oba 2, 2 2 − 1 (2 2 − 1 = 3) są liczbami pierwszymi. Ale nie możemy odpowiedzieć, jeśli poproszono nas o sprawdzenie, czy istnieją jakieś nieparzyste liczby idealne.
Wiemy też, że każdy język ma limit liczb całkowitych, które może przechowywać. Z tym ograniczeniem możemy nie mieć możliwości znalezienia największej liczby idealnej.
Wszystkie te ograniczenia napotykamy, jeśli nasza liczba wejściowa jest duża, ale jeśli nasza liczba wejściowa jest mała, nasze początkowe rozwiązanie działałoby w krótszym czasie.
Przeczytaj także: Framework Pythona do tworzenia stron internetowych
Wniosek
Znamy definicję i rozumiemy pojęcie idealnej liczby. Przeprowadzony przez podstawowe rozwiązanie do znajdowania liczby jest liczbą idealną, czy nie. A po obejrzeniu początkowego rozwiązania trochę je zoptymalizowaliśmy, zmniejszając liczbę iteracji. Przeszliśmy przez ograniczenia naszego algorytmu i omówiliśmy wzór Euklidesa na znalezienie liczby parzystej idealnej.
Teraz, gdy znasz już program Pythona, który sprawdza, czy liczba jest liczbą idealną, czy nie. Spróbuj napisać kod samodzielnie i spróbuj go zoptymalizować, jeśli znajdziesz jakieś nakładające się iteracje. Spróbuj także zbudować kod do znajdowania idealnych liczb w podanym zakresie liczb.
Jeśli chcesz dowiedzieć się więcej o Pythonie, nauce o danych, sprawdź program Executive PG w dziedzinie Data Science IIIT-B i upGrad, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży , 1 na 1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.
Wyjaśnij złożoność programu liczb doskonałych w Pythonie.
Mówi się, że liczba jest liczbą doskonałą, jeśli jest równa sumie jej dzielników. Aby sprawdzić, czy liczba jest idealna, czy nie, mamy dwa podejścia. Pierwsze podejście jest podejściem naiwnym, w którym złożoność czasowa wynosi O(n2), ponieważ iterujemy czasy „j” dla każdego „i” i sprawdzamy jego dzielniki.
Drugie podejście to rozwiązanie zoptymalizowane, w którym złożoność czasowa wynosi O(√n). Tutaj nie musimy powtarzać każdej liczby. Możemy to bezpośrednio wywnioskować za pomocą wzoru Euklidesa, który jest:
2n−1(2n−1), gdzie n i 2n są liczbami pierwszymi.
Jednak ten wzór nie działa dla liczb nieparzystych doskonałych i dlatego musimy znaleźć dla nich inne podejście.
Jakie są ograniczenia podejść Programu Doskonałej Liczby?
Oba te podejścia są dobre, ale tylko do pewnego stopnia. Żadnego z nich nie można uznać za idealne podejście ze względu na pewne szczegóły techniczne. Ograniczenia tych podejść są następujące:
1. Pierwsze i naiwne podejście jest gorsze, ponieważ pochłania dużo czasu i pamięci oraz ma złożoność czasową O(n2). Dzieje się tak, ponieważ używamy pętli zagnieżdżonej i iterujemy pętlę wewnętrzną n razy dla każdego elementu pętli zewnętrznej. To podejście jest naiwne i da TLE dla większych wartości n i dlatego nie jest zalecane.
2. Następnie mamy zoptymalizowane podejście, które rozwiązuje problem w O(√n). Jest to dobre podejście, chyba że w grę wchodzą nieparzyste liczby idealne. Nie możemy sprawdzić nieparzystych liczb doskonałych za pomocą tego podejścia, ponieważ jest ono oparte na „wzorze Euklidesa na liczby nawet doskonałe”, które działa tylko dla liczb parzystych doskonałych.
Czy Python nadaje się do programowania konkurencyjnego?
Python wyewoluował z C/C++, a nawet Javy i jest uważany za najlepiej dostosowany język do celów badawczo-rozwojowych. Ale jeśli chodzi o programowanie konkurencyjne, większość społeczności programistów unika Pythona. Powodem, dla którego Python jest najwolniejszy spośród tych trzech języków.