Zmiany w programie Dzielnik.

0

Cześć jest ktoś w stanie wyjaśnić mi jak mam nanieść te poprawki co mam zmienić bo niezbyt rozumiem jak mam nanieść te poprawki do drugiej pętli w kodzie poniżej:

"
Rozwiązanie ma złożoność liniowę O(n) a należy to zrobić ze złożonością pierwiastkową O(sqrt(n)).
Druga pętla ma być od sqrt(n) do 1. Zmienna sterująca "i" pętli ma się zmieniać od sqrt(n) do 1. Jesli "i" jest dzielnikiem liczby n , to również "n/i" jest dzielnikiem liczby "n" (w tej drugiej pętli należy wyświetlić właśnie "n/i")."

#include <clocale>
#include <iostream>
#include <string>

void dzielniki(unsigned long long liczba)
{
	std::cout << "Dzielniki liczby " << liczba << " to: ";
	for (unsigned long long i = 1; i <= sqrt(liczba); i++)
	{
		if (liczba % i == 0)
		{
			std::cout << i << ", ";
		}
	}
	for (unsigned long long i = sqrt(liczba) + 1; i <= liczba; i++)
	{
		if (liczba % i == 0)
		{
			std::cout << i << ", ";
		}
	}
}

int main()
{
	std::setlocale(LC_ALL, "pl_pl");

	unsigned long long liczba;
	std::cout << "Podaj liczbę:";
	std::cin >> liczba;

	dzielniki(liczba);
}

0

Czemu chcesz to robić w dwóch pętlach, w ten sposób, zawsze będziesz miał, O(n), od, 1 do pierwiastka, i od pierwiastka do, n; sprwawdzenie czy, n / i również jest dzielnkiem rób w pierwszej, i jedynej, pętli, jak tutaj (nie zaglądaj, jak chcesz się pobawić :)):
https://www.geeksforgeeks.org/find-all-divisors-of-a-natural-number-set-2/

0

musze mieć w dwóch pętlach bo tak chce profesor(miałem wcześniej w jednej wszystko i działało i była petarda ale on że nie że ma być w dwóch i takie uwagi mi napisał, poprawiam to 2 albo 3 raz i już sam nwm jak mam to napisać

Co Ci mogę napisać, nie tyle, że się spodziewałem takiej odpowiedzi, byłem jej pewien :D Przy takich założeniach, niech mnie ktos poprawi, jeżeli sie mylę, zdanie jest sprzeczne, bo nie da się uzyskać, O(sqrt(n)), jesli druga pętla idzie od piewiastka do, n. Mogła by iść znowu od jeden do pierwiastka, wtedy tak.

0
lion137 napisał(a):

musze mieć w dwóch pętlach bo tak chce profesor(miałem wcześniej w jednej wszystko i działało i była petarda ale on że nie że ma być w dwóch i takie uwagi mi napisał, poprawiam to 2 albo 3 raz i już sam nwm jak mam to napisać

Co Ci mogę napisać, nie tyle, że się spodziewałem takiej odpowiedzi, byłem jej pewien :D Przy takich założeniach, niech mnie ktos poprawi, jeżeli sie mylę, zdanie jest sprzeczne, bo nie da się uzyskać, O(sqrt(n)), jesli druga pętla idzie od piewiastka do, n. Mogła by iść znowu od jeden do pierwiastka, wtedy tak.

dokładnie taki dostałem komentarz do działającego programu

"Należy zaimplementować funkcję wypisującą dzielniki liczby N, która ma złożoność pierwiastkową (pętla od 1 do pierwiastka z N a nie od 1 do N). Proszę uruchomić funkcję dla N równego 10 do 18 (1 000 000 000 000 000 000).
Tak jak Panu tłumaczyłem, należy użyć dwóch pętli. Pierwsza od 1 do pierwiastka z N a druga od pierwiastka z N do 1. W pierwszej pętli należy wypisać dzielniki mniejsze równe pierwiastek z N a w drugiej dzielniki większe od pierwiastka z N."

0
Papito napisał(a):

Pierwsza od 1 do pierwiastka z N
a druga od pierwiastka z N do 1.

Powiedz którego słowa nie zrozumiałeś w zacytowanej wypowiedzi profesora?

1

@Papito:
Ach, sorki, źle zrozumiałem, tak w ten sposób rzeczywiście będzie będzie, O(sqrt(n)), tak jak w podlinkowanym poście, w drugiej pętli sprawdzaj, n / i.

0
lion137 napisał(a):

@Papito:
Ach, sorki, źle zrozumiałem, tak w ten sposób rzeczywiście będzie będzie, O(sqrt(n)), tak jak w podlinkowanym poście, w drugiej pętli sprawdzaj, n / i.

Dobrze zrozumiałem ? Kod z drugiej pętli

for (unsigned long long i = sqrt(liczba) + 1; i <= liczba; i++)
	{
		if (liczba / i == 0)
		{
			std::cout << i << ", ";
		}
	}
!
0

Dobra, testowałeś to, zwraca dobre wyniki, co z ta dziewiątka, o której wspomniałem w komentarzu?

0
lion137 napisał(a):

Dobra, testowałeś to, zwraca dobre wyniki, co z ta dziewiątka, o której wspomniałem w komentarzu?

Po podaniu liczby 9 zwraca jedynie 1 i 3 bez 9

0

Właśnie, maja być tylko dzielniki właściwe (tu będzie bez dziewięć), czy wszystkie, to objemuje też dziewięć, które jest dzielnikiem niewłaściwym.

1

Skoro profesor napisał od 1 do sqrt() i od sqrt() do 1 to po kiego się zastanawiacie?

0
lion137 napisał(a):

Właśnie, maja być tylko dzielniki właściwe (tu będzie bez dziewięć), czy wszystkie, to objemuje też dziewięć, które jest dzielnikiem niewłaściwym.

ok czyli przy liczbie 6 nie będzie 3 a przy 8 nie będzie 4

0

@_13th_Dragon:
No tak, czyli dzielnik niewłaściwy też wchodzi, można się rozejść:)

@Papito:

ok czyli przy liczbie 6 nie będzie 3 a przy 8 nie będzie 4

Co? Czemu?

0

@lion137, po 3-im razie ty już zrozumiałeś ... :D

1

Przecież O(n) w tym wypadku to jest zdecydowanie złożoność wykładnicza, a mianowicie jest to O(2^m) gdzie m to długość zapisu liczby n (standardowa notacja). Mówienie na to "liniowa" to jest plucie na całą historię teorii złożoności.

0

@Suchy702
Nie czytałem kodu OPa, ale załóżmy że jak tak jak mowisz, czyli O(n). To co chciałem wyrazić, że nazwanie tego O(n) złożonością liniową jest nieodpowiednie. Długość zapisu liczby n, to jest log2(n). Złożoność w informatyce liczy się względem długości zapisu. Jak pomyślisz o tym chwilkę, to to ma bardzo duży sens. W przypadku takiego sortowania, masz tablicę liczb jakiejś długości. Zwiększysz dwa razy zapis takiej tablicy (tzn zwiększysz jej długość dwa razy), i oczekujesz że wraz z tą długością wzrośnie czas sortowania o jakiś czynnik. To czemu w przypadku faktoryzacji liczb, nagle zamiast brać pod uwagę długość zapisu liczby, zaczynasz się przejmować jej wartością (tzn, np. interpretacją jej zapisu binarnego)?

W ten sam sposób, algorytm co działa w czasie O(sqrt(n)) również jest wykładniczy, tylko że zamiast być O(2^m), jest O(sqrt(2)^m), gdzie m=log2(n).

0

Zauważ. że jak sie mieścisz w słowie maszynowym, powiedzmy, 64 bity, tpo złożonośc operacji na liczbie jest stała.

0

@enedil
Rozumiem że małbym popatrzeć na liczbę, jako tablicę zer i jedynek reprezentującą ją w postaci binarnej. Wytedy odpowiednio duże zwiększenie liczby, zwiększyłoby rozmiar tablicy.
Tylko złożoność O(2^m) sugeruje że musimy przejść po wszystkich stanach tej tablicy (wiem że pesymistycznie tak może się zdarzyć), O(n) jest dokładniejsze, bo zawsze zrobimy O(n) razy. Nawet bardziej intuicyjnie jest powiedzieć że operacje wykonują sie O(n) razy, ale rozumiem że nie chodzi ci intuicje, tylko o poprawność z teorią złożoności. Nie rozumiem dlaczego mielibyśmy używać O(2^m) które jest mniej czytelne i mniej intuicyjne niż O(n), bo nie mam żadnej wiedzy z teorii złożoności, mógłbyś dać jakiś link, rozszerzający temat?

EDIT:
Nawet na wikipedii odnośnie rozkładu na czynniki pierwsze mówią:
Wszystkie znane algorytmy działają w czasie wykładniczym wobec długości rozkładanej liczby.
a nie O(sqrt(n))
Co dziwne, nie ma (lub nie umiem znaleźć) artykułu w wikipedii odnośnie szukania wszystkich dzielników na wikipedii.

0

@Suchy702:

  1. jak najbardziej można pisać O(n), jest to poprawny zapis. Możesz powiedzieć "złożoność liniowa względem wartości liczby", "złożoność wykładnicza", "złożoność wykładnicza względem długości zapisu liczby", ale nie możesz powiedzieć po prostu "złożoność liniowa".

  2. Ale przecież jak piszesz O(n) jest to dokładnie O(n) razy, a jak piszesz O(2^m) to robisz to dokładnie O(2^m) razy. Myślę że jak masz siwobrody doświadczenie z teorią złożoności to nie masz problemów z oboma zapisami, a ten drugi jest bardziej użyteczny, bo możesz go używać do klasyfikacji problemów. Np. nie jest znane czy faktoryzacja jest problemem który należy do P, ale już wiemy że należy do NP. Wiemy też że należy do coNP (tzn stwierdzanie czy liczba złożona nie ma dzielnika mniejszego niż k różny od 1 należy do NP).

  3. O(sqrt(n)) jest właśnie wykładnicze. Bo długość n, to log2(n). Więc złożoność to O(2^(sqrt(n))) = O(sqrt(2)^n), czyli wykładniczo z wykładnikiem sqrt(2), a nie z wykładnikiem 2.

  4. Wikipedia się myli. Istnieją algorytmy faktoryzacja które działają w czasie subwykładniczym, tzn w O(c^n) dla każdej liczby c. Przykładowo
    https://en.m.wikipedia.org/wiki/General_number_field_sieve
    Ale nie myli się w pewnym sensie, bo nie znamy żadnego algorytmu który działa w czasie wielomianowym. O ile P != NP to istnieją klasy złożoności pomiędzy nimi.

0

@enedil: A można powiedzieć, że algorytm szukania dzielników n ma złożoność O(n), tak jak w pierwszym poście wątku? Wtedy wiadomo by było, że o wartość liczby, a nie chodzi o długość zapisu (co czasem bywa użyteczne).

0

@enedil , przecież jeśli mówimy o modelu RAM, tak jak problem OP - a, to operacje na liczbach o dowolnej, ale ograniczonej długości są stałe; jeśli mówimy o bigintach to spoko, długość liczby ma znaczenie. Z kontekstu powinniśmy wiedzieć, o który model chodzi. Ryan O'Donnell o tym mówi:

0

@Krzemień: Można powiedzieć. Ja się tylko czepiam stwierdzenia "algorytm jest liniowy", bo jak nie powie się względem czego jest liniowy, to znaczy że liniowy względem długości zapisu.

0
lion137 napisał(a):

@enedil , przecież jeśli mówimy o modelu RAM, tak jak problem OP - a, to operacje na liczbach o dowolnej, ale ograniczonej długości są stałe; jeśli mówimy o bigintach to spoko, długość liczby ma znaczenie. Z kontekstu powinniśmy wiedzieć, o który model chodzi. Ryan O'Donnell o tym mówi:

Jeśli myślimy o liczbach dowolnej ale ograniczonej długości, to każdy algorytm który terminuje działa w czasie stałym. Ergo, wytłumacz mi proszę czemu wtedy operacje arytmetyczne w czasie stałym to by miało być coś co jest interesujące. Also, nie wiem czy zauważyłeś, ja nawet się nie czepiam tego ile czasu zajmuje jedno mnożenie czy dzielenie - ja się czepiam tego ile zajmuje faktoryzacja.

1 użytkowników online, w tym zalogowanych: 0, gości: 1