Liczby doskonałe - zastosowanie własnych funckji

Question

Witam,

---

Dostałem zadanie, w którym mam napisać program sprawdzający czy liczba podana z klawiatury jest doskonała. Jednakże kond, który napisałem nie dostał 100pkt, a jedynie 80. Powodem był najprawdopodobnie zbyt wysoki czas działania, bo zmienne mam w long long'u. Otwieram pytanie, ponieważ próbowałem użyć printf(), scanf(), (a nawet "\n" zamiast endl), ale żadna z tych zmian nie skutkowała lepszym wnikiem.

---

Oto zadanie:

Dane są liczby całkowite a, b oraz c. Wiemy, że a=b⋅ c. W takim wypadku a nazywamy wielokrotnością b oraz c, zaś b oraz c są dzielnikami właściwymi liczby a (przy założeniu, że b, c > 1). Liczba doskonała to liczba naturalna, która jest równa sumie wszystkich swoich dzielników właściwych. Dodatnia liczba całkowita jest niedoskonała, jeżeli suma jej dzielników właściwych jest mniejsza lub większa niż sama liczba. Tak więc suma dzielników 9 jest niedostateczna, a 12 jest za duża.

---

Dane

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita bez znaku n (1 ≤ n ≤ 1000). W kolejnych n liniach znajduje się po jednej liczbie całkowitej x (4 ≤ x ≤ 109 ).

Wynik

Dla każdej podanej liczby x wypisz, czy jest ona doskonała („OK”), suma dzielników jest zbyt mała („NIEDOSTATECZNA”) lub za duża („WIELKA”).

---

Przykład

Dla danych wejściowych: 

3

6 9 12

poprawną odpowiedzią jest:

OK

NIEDOSTATECZNA

WIELKA

---

Bardzo dziękuję za podsyłane przez Was odpowiedzi oraz komentarze na temat w jaki sposób uprościć/przyspieszyć działanie kodu.

---

Mój kod:

#include<bits/stdc++.h>
using namespace std;
long long dosk(long long y)
{
    if(y==1) return 0;
    long long suma=0;
    //ide do pierwiastka z y, zeby mniej czasu zabieralo
    for(int i=2; i*i<=y; i++)
    {
        if(y%i==0)
        {
            suma+=i;
            if(y/i!=i)
            {
                suma+=y/i;
            }
        }
    }
    return suma+1;
}

int main()
{
    int ile; cin>>ile;
    long long y;
    for(int i=1; i<=ile; i++)
    {
        cin>>y;
        if(dosk(y)==y) cout<<"OK\n";
        else if(dosk(y)>y) cout<<"WIELKA\n";
        else cout<<"NIEDOSTATECZNA\n";
    }
}

---

PS. Zrobiłem program działający na identycznej zasadzie, tylko, że void'em i dało mi 100pkt. Nie wiem czym może być to spowodowane.

Comments

@mokrowski, dzieki, porównam czasy i odpowiem

---

Ale in (+) czy (-) ? Czyli szybciej jest czy wolniej?

---

nie rozumiem pytania, a dokładnie o co chodzi z tymi znakami +/-

---

"in plus" czy "in minus" :) Na pierwszy rzut oka... czasy porównywalne ale sprawdź...

---

@polandonion, Odnosnie podwójnego liczenia.
Tak, ja rozumiem, że trzeba podać czy wieksza czy niedostateczna, ale do tego trzeba porównać wynik dosk dwa razy, a nie wyliczyć dosk dwa razy.

Weźmy ten Twoj fragment.

if(dosk(y)==y) cout<<"OK\n"; // liczysz dosk(y)
else if(dosk(y)>y) cout<<"WIELKA\n";  // liczysz dosk(y), ktory da 
                                      // taki sam wynik jak wyzej
else cout<<"NIEDOSTATECZNA\n";

Gdy y jest niedoskonała wyliczysz dosk dwa razy, co jest kompletnie niepotrzebne.
Porównaj z kodem niżej.
 

long long doksValue = dosk(y)
if (doskValue == y) cout << "OK\n";
else if (doskValue > y) cout << "WIELKA\n";
else cout << "NIEDOSTATECZNA\n";

Jak mi nie wierzysz, że program działać bedzie lepiej to sobie zedytuj dosk funkcję następująco:

long long dosk(long long y)
{
  // Licznik wykonań
  static int count = 0;
  ++count;
  cout << "Wykonano dosk " << count << " razy" << endl;

  // Reszta Twojego kodu
  if (y == 1) return 0;
  ....

 

Zobaczysz, że efekt prrogramu bedzie taki sam (w sensie tak samo bedzie rozpoznawał liczby) ale zazwyczaj bedzie mniej wykonań dosk.

Co do Twojego kodu z zegarem, to jeśli używasz w miare nowoczesnej wersji c++ (czyli ++11 lub nowszy), to zamiast starego clock radze używać clocków z chrono.
Dodatkowo jak masz 2 algorytmy i chcesz porównać ich wydajnośc, to lepiej każdy uruchomić wielokrotnie, a wynik uśrednić. Im więszka wielokrotność tym lepiej :) Dobrą techniką doboru tej wielokrotności jest zacząć od X (np. 1000) i zwięszkać o rząd wielkości (x10), aż długośc wykonania będzie akceptowalna (np. do minuty). Uruchom sobie swój test pomiarowy, który teraz masz, dwa razy i zobaczysz, że bedziesz mial troche różne wyniki. Potrafią się one różnić nawet sporo, dlatego, o ile jeden algorytm nie jest przytłaczająco wolniejszy od drugiego (a to widać raczej bez testu), to lepiej wykonać test wielokrotnie..

Answer 1

Możesz przyśpieszyć działanie programu wykonując potrzebne obliczenia w trakcie kompilacji - używając do tego celu tablicy typu constexpr i lambdy jak funkcji wyliczeniowej. Wtedy samo wykonanie programu będzie stałe O(1).

#include <iostream>
#include <math.h>
#include <array>

using namespace std;

constexpr int numbers {109};

static constexpr auto PerfectNumberCheck = []{
    array<const char*,numbers+1> a{};
    for( int number {0} ; number < a.size() ; ++number )
    {
        int sum {0};
        for( int i {2} ; i <= sqrt(number) ; ++i ) if( number%i == 0 ) sum += ( i==(number/i) ? i : (i + number/i) );
        if( sum+1 == number ) a[number] = "OK";
        else if( sum+1 > number ) a[number] = "WIELKA";
        else a[number] = "NIEDOSTATECZNA";
    }
    return a;
}();

int main()
{
    for( const auto& number : {4,6,9,23,28,99,100} )
    {
        cout << number << " -> " << PerfectNumberCheck.at(number) << endl;
    }
}

https://godbolt.org/z/8TGbf1sea