Wykaz czy liczba jest doskonała czy niedoskonała

Question

Witam,

Moim zdaniem było

Napisz funkcję o nagłówku def suma_dzielnikow(m): zwracającą sumę wszystkich dzielników liczby m należących do przedziału .

Oraz połączone z tym zadaniem kolejne zadanie 

Napisz funkcję o nagłówku def czy_doskonala(m): zwracającą odpowiedź na pytanie, czy liczba m jest doskonała. Skorzystaj z funkcji suma_dzielnikow!.

Z pierwszym zadaniem sobie poradziłem, z drugim mniej więcej ale nie wiem gdzie popełniam błąd że nie wyswietla czy jest True czy False.

m = int(input("Wprowadz liczbe"))

print("Dzielnikami szukanymi przez ciebie są ")
suma = 0

def suma_dzielnikow(m):
    return
for i in range(1, m-1):
    if (m % i == 0):
        print(i)
        suma+=i

def czy_doskonala(m):
    if suma_dzielnikow(m) == m:
        return True
    elif suma_dzielnikow(m) != m:
        return False
        

print("Czy Doskonala",czy_doskonala(m))
print("Sumą dzielinków poszukiwanych przez ciebie " + str(suma))

 

Comments

Tylko mała podpowiedź z mojej strony, wystarczy sprawdzić dzielniki do m/2.

---

Nie bardzo rozumiem, co masz na myśli. 

Jak sprawdzić dzielnik do m/2?

W sensie żeby zwrócił coś? 

def czy_doskonala(m):
    if suma_dzielnikow(m) == m:
        return True
    elif suma_dzielnikow(m) != m:
        return False

zamienić na

def czy_doskonala(m):
    return suma_dzielnikow(m) == m

 

---

Chcesz program zabawkowy w C++ do testowania liczb doskonałych?

---

@Meffy, do sprawdzenia czy liczba jest doskonała, wymagane jest sumowanie dzielników właściwych. Nie obejmują one samej wartości (a ta z całą pewnością dzieli się przez siebie).

Z kolei sprawdzanie czy liczba się dzieli przez inną przekraczającą jest połowę i mniejszą od samej liczby, nie ma sensu bo z pewnością takiej nie znajdziesz. Następną jest sama liczba a jej nie bierzesz pod uwagę .. bo chodzi o dzielniki właściwe.

https://pl.wikipedia.org/wiki/Liczba_doskona%C5%82a

---

@Meffy,
Jakby ktoś chciał drążyć temat, to obecnie znanych jest tylko 51 liczb doskonałych:
https://en.wikipedia.org/wiki/List_of_perfect_numbers
wszystkie one są parzyste. Znane są formuły które musi spełniać liczba parzysta i nieparzysta aby mogła w ogóle pretendować do liczby doskonałej:
https://pl.wikipedia.org/wiki/Liczba_doskona%C5%82a
 

Optymalny algorytm sprawdzi tylko liczby pasujące do formuły. Niestety, pomimo że formuła odsieje znaczną większość liczb, to dla liczb pasujących, trzeba zrobić karkołomną faktoryzację w celu ostatecznego testu. Ale po tabelce widać, że niektórym się to udało.

 

Answer 1

Do naiwnej implementacji, wystarcza zauważenie że zbędne jest testowanie zakresu powyżej połowy dzielników. Stąd proste mało wydajne i "nie-pythonowe" rozwiązanie, może wyglądać tak:

#!/usr/bin/env python3

def suma_dzielnikow_wlasciwych(liczba):
    dzielniki = []
    for dzielnik in range(1, (liczba // 2) + 1):
        if (liczba % dzielnik) == 0:
            dzielniki.append(dzielnik)
    return sum(dzielniki)

def czy_doskonala(liczba):
    return suma_dzielnikow_wlasciwych(liczba) == liczba

if __name__ == '__main__':
    for liczba in range(1, 9000):
        if czy_doskonala(liczba):
            print(liczba)

Tu sprawdzam zakres [1, 9000).

Trochę bardziej idiomatyczny kod to:

#!/usr/bin/env python3

def suma_dzielnikow_wlasciwych(liczba):
    return sum(dzielnik for dzielnik in range(1, (liczba // 2) + 1) if (liczba % dzielnik) == 0)

def czy_doskonala(liczba):
    return suma_dzielnikow_wlasciwych(liczba) == liczba

if __name__ == '__main__':
    for liczba in range(1, 9000):
        if czy_doskonala(liczba):
            print(liczba)

Coś jeszcze pewnie dało by się wydusić z tego naiwnego algorytmu. Na średnim komputerze, ten zakres liczy się ok 1.3 sec. 

Answer 2

Tutaj zabawkowy program do testowania całych przedziałów. W pythonie można się wzorować na tym kodzie. Sprawdzenie przedziału od 2 do miliona trwa niecałą minutę. Czy działą poprawnie dla wszystkich liczb - nie wiem. Można tam dodać test pierwszość millera-rabina - powinno przyspieszyć oblicznenia:

Kompilacja i uruchomienie:

c++ -std=c++11 -O3 main.cpp -o perfectNumber
./perfectNumber 
Podaj minimum przedziału: 2
Podaj maksimum przedziału: 1000000
6 is perfect! 1, 2, 3 primes[9, 23]
28 is perfect! 1, 2, 4, 7, 14 primes[9, 23]
496 is perfect! 1, 2, 4, 8, 16, 31, 62, 124, 248 primes[1009, 8011]
8128 is perfect! 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064 primes[1009, 8011]
benchmark: 58.0424


Podaj minimum przedziału: ^C
m@SSDB:~/Dokumenty/c/eduPerfectNumber$ c++ -std=c++11 -O3 main.cpp -o perfectNumber
m@SSDB:~/Dokumenty/c/eduPerfectNumber$ ./perfectNumber 
Podaj minimum przedziału: 2
Podaj maksimum przedziału: 1000000
6 is perfect! 1, 2, 3 primes[9, 23]
28 is perfect! 1, 2, 4, 7, 14 primes[9, 23]
496 is perfect! 1, 2, 4, 8, 16, 31, 62, 124, 248 primes[1009, 8011]
8128 is perfect! 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064 primes[2009, 17471]
benchmark: 96.1287


Podaj minimum przedziału: ^C
m@SSDB:~/Dokumenty/c/eduPerfectNumber$ c++ -std=c++11 -O3 main.cpp -o perfectNumber
m@SSDB:~/Dokumenty/c/eduPerfectNumber$ ./perfectNumber 
Podaj minimum przedziału: 2
Podaj maksimum przedziału: 10000
6 is perfect! 1, 2, 3 primes[9, 23]
28 is perfect! 1, 2, 4, 7, 14 primes[9, 23]
496 is perfect! 1, 2, 4, 8, 16, 31, 62, 124, 248 primes[1009, 8011]
8128 is perfect! 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064 primes[1009, 8011]
benchmark: 0.0299189


Podaj minimum przedziału: 2   
Podaj maksimum przedziału: 100000
6 is perfect! 1, 2, 3 primes[1009, 8011]
28 is perfect! 1, 2, 4, 7, 14 primes[1009, 8011]
496 is perfect! 1, 2, 4, 8, 16, 31, 62, 124, 248 primes[1009, 8011]
8128 is perfect! 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064 primes[1009, 8011]
benchmark: 0.961177


Podaj minimum przedziału: 2
Podaj maksimum przedziału: 1000000
6 is perfect! 1, 2, 3 primes[6009, 59441]
28 is perfect! 1, 2, 4, 7, 14 primes[6009, 59441]
496 is perfect! 1, 2, 4, 8, 16, 31, 62, 124, 248 primes[6009, 59441]
8128 is perfect! 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064 primes[6009, 59441]
benchmark: 58.4139

 

Kod źródłowy

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <chrono>
#include <cmath>

using utyp = unsigned int;
using ultyp = unsigned long long;
using cultyp = const ultyp;

static std::vector<ultyp> primes = {2,3,5,7,11,13,17,19,23};

static void addPrimes() {
    utyp found=0;
    ultyp next = primes[ primes.size() - 1 ] + 2;
    while( found < 1000 ) {
        size_t i=0;
        while( i<primes.size() && next % primes[i] ) {
            i++;
        }
        if( i == primes.size() ) {
            primes.push_back( next );
            found++;
        }
        next += 2;
    }
}

static void insert( std::vector<ultyp> &r , cultyp prime , cultyp v ) {
    const size_t size = r.size();
    for( size_t i=0 ; i<size ; i++ ) {
        if( v > prime * r[i] ) {
            if( std::find( r.begin() , r.end() , prime * r[i] ) == r.end() ) {
                r.push_back( prime * r[i] );
            }
        }
    }
}

static bool millerRabinTest(cultyp v) {
    //not implemented yet
    //example: https://github.com/cslarsen/miller-rabin/blob/master/miller-rabin.cpp
    return false;
}

static void divides( ultyp v , std::vector<ultyp> &d ) {
    cultyp cpyV = v;
    d.resize(1);
    d[0] = 1;
    ultyp i=0;
    while( primes[i] <= v && primes[i] <= cpyV/2 ) {
        if( v % primes[i] == 0 ) {
            v /= primes[i];
            insert( d , primes[i] , cpyV );
        } else if( millerRabinTest( v ) ) {
            insert( d , v , cpyV );
            break;
        } else if( ++i >= primes.size() ) {
            addPrimes();
        }
    }
}

static bool isPerfect( cultyp v ) {
    static std::vector<ultyp> d;
    divides( v , d );
    ultyp sum = 0;
    for( size_t i=0 ; sum <= v && i < d.size() ; i++ ) {
        sum += d[i];
    }
    return v == sum;
}

int main(int argc, char *argv[]) {
    (void)argc;
    (void)argv;
    while( true ) {
        ultyp min,max;
        std::cout << "Podaj minimum przedziału: ";
        std::cin >> min;
        std::cout << "Podaj maksimum przedziału: ";
        std::cin >> max;
        const auto start = std::chrono::system_clock::now();
        for( ultyp i=min ; i<=max ; i++) {
            if( isPerfect( i ) ) {
                std::cout << i << " is perfect! ";
                std::vector<ultyp> d;
                divides( i , d );
                std::sort( d.begin() , d.end() );
                for( size_t i=0 ; i<d.size() ; i++ ) {
                    if( i > 0 ) {
                        std::cout << ", ";
                    }
                    std::cout << d[i];
                }
                std::cout << " primes[" << primes.size() << ", " << primes[primes.size()-1]  << "]";
                std::cout<< std::endl;
            }
        }
        {
            const auto end = std::chrono::system_clock::now();
            const std::chrono::duration<double> elapsed = end - start;
            std::cout << "benchmark: " << elapsed.count() << std::endl;
        }
        std::cout << std::endl << std::endl;
    }
    return 0;
}

 

Comments

Ja jestem ciekawy ile czasu potrzebuje ten program na sprawdzenie liczb z przedziału od 2 do miliona. Jeśli to jest za trudne, to chociaż ile czasu potrzebuje dla sprawdzenia takich liczb:

6
12
28
48
496
850
8128
15666
33550336
75321343
8589869056
9031391346
137438691328
231343142348

Jeśli mogę poprosić, to będę wdzięczny.

---

No ja rozumiem twoje wątpliwości, ale w poleceniu jest żeby zrobić tak ze jest (1;m-1), to robię według danego polecenia nie przekształcam tego pod siebie. Możliwe ze dużą ilość czasu bedzie to wyszukiwane

---

Nie mam wątpliwości, ani zlośliwości, ani nie krytykuję, kod wygląda ładnie i poprawnie. To że nie używa optymalnego algorytmu to nieważne, optymalizacja to temat trudny. Pytam z czystej ciekawości, chcę się dowiedzieć ile czasu ten program będzie działał dla powyższych liczb.

---

@mmarszik, rozumiem że (ogólnie) zdajesz sobie sprawę z różnic pomiędzy językami Python i C/C++? Także co do kosztu wykonania jakichkolwiek operacji. Przyjmuje się że 50 - 100 razy dłuższe działanie i większa konsumpcja pamięci to rzecz normalna (na niekorzyść Pythona). Dla języka Python, argument szybkości wykonania nie jest aż tak ważki w stosunku do czasu implementacji programu przez człowieka. Tu kontekst jest jasny. Użyć konkretnych funkcji i prostego naiwnego algorytmu.

https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/python3-gcc.html

---

Mniej więcej zdaję sobie sprawę, czasami jakieś bencharki widywałęm. Nadażyła się teraz okazja, chciałem zobaczyć kolejny benchamrk. Temat tego czy w pythonie jest ważna wydajność czy też nie - pomijam, bo jest zbyt rozległy na szybką dyskusję. Jeśli mogę, to ponownie proszę o czasy wykonania.