jak mogłbym poprawic kod aby była jak najmniejsza złożonosc? Proszę expertow o pomoc.
#include <iostream>
using namespace std;
int main()
{
cout << "Sprawdz czy liczba jest doskonala" << endl;
int d=0,n;
cout << "Podaj n: ";
cin >> n;
for (int i=1; d<n; i++)
{
if (n%i==0)
d=d+i;
}
if (d==n)
cout << "TAK";
else
cout << "NIE";
return 0;
}
for (int i = 1; i < n; i++)
tu możesz zrobić
for (int i = 1; i <= n/2; i++)
Dalej, wiki twierdzi że
"Jak dotąd nie udało się znaleźć liczby doskonałej nieparzystej, ani dowodu, że liczby takie nie istnieją. [...] Wiadomo też, że jeśli liczba taka istnieje, to musi być
większa od 10^1500"
stąd można bezpiecznie założyć, że każda wprowadzona przez usera liczba nieparzysta NIE JEST doskonała. Możesz to sprawdzić na początku.
if (n % 2 != 0) { cout << "NIE"; return 0; }
Możesz wykorzystać również to, że liczby doskonałe rózłożone są dość "rzadko" w liczbach naturalnych. Najmniejsze liczby doskonałe to
6, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128 (https://en.wikipedia.org/wiki/List_of_perfect_numbers), kolejna już nie mieści się w największym standardowo dostępnym typie danych na 64 bitach, tj unsigned long long.
dziekuje
cos nie działa bo dla 6 wypisuje ze nie jest
mam taki kod ale cos sie psuje w nim ;c
#include <iostream>
using namespace std;
int main()
{
cout << "Sprawdz czy liczba jest doskonala" << endl;
int d=0,n;
cout << "Podaj n: ";
cin >> n;
if (n % 2 != 0)
{
cout << "NIE";
return 0;
}
for (int i=1; d<n; i+=2)
{
if (n%i==0)
d=d+i;
}
if (d==n)
cout << "TAK";
else
cout << "NIE";
return 0;
}
Ze względu na zakresy zmiennych, możliwych liczb jest 8, więc można to zrobić jednym ifem ;)
Jeśli natomiast przejmujesz się problemem samym w sobie, czyli jak go rozwiązać bez tablicowania, to muszę stwierdzić, że niestety nie wiadomo jak najszybciej ten problem rozwiązać, gdyż do efektywnego rozwiązania potrzeba znać rozkład n na czynniki pierwsze.
Przykład: 8128 = 2^6 * 127. Suma dzielników wyraża się wzorem (2^7 - 1)/(2-1) * (127^2 - 1)/(127 - 1) = 127 * 128 = 2*8128. Suma dzielników właściwych, to poprzednia suma, po odjęciu n: 2*8128 - 8128 - 8128 = n. Zatem wystarczy rozłożyć n na czynniki.
Zobacz tutaj: https://en.wikipedia.org/wiki/Perfect_number#Even_perfect_numbers, liczby doskonałe, muszą być postaci 2^(p - 1) * (2^p - 1), gdzie 2^p - 1 jest liczą pierwszą, ta kwięc korzystając z tego: https://www.mersenne.org/primes/ , Masz test w stałym czasie:).