[C++] Wyznaczanie liczb zaprzyjaźnionych z zakresu 1 do n

[Krzychu25]

No więc mam takie zadanie, w którym muszę z zakresu od 1 do n wyłowić liczby zaprzyjaźnione. Muszę to zrobić za pomocą pętli for i if'ów, lecz nie wiem jak się zabrać. Coś napisałem, co wg mojej logiki powinno działać, jednakże nie działa.

"Liczby zaprzyjaźnione to para różnych liczb naturalnych, takich że suma dzielników każdej z tych liczb równa się drugiej (nie uwzględniając tych dwóch liczb jako dzielników).

Pierwszą parą takich liczb, która została podana już przez Pitagorasa, jest para liczb 220 i 284, ponieważ:
220 = 1 + 2 + 4 + 71 + 142 (dzielniki 284)
284 = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 (dzielniki 220)"

Takie coś mam:

Kod: Zaznacz cały

#include<iostream>
#include<cstdlib>

using namespace std;

int main()
{
    int n,suma1=0, suma2=0;
    cin>>n;
    
    for(int a=1;a<n-1;a++)//kolejne liczby
    {
    for(int e=1;e<a;e++)//dzielniki
    {
    if(a%e==0)
    {
    suma1+=e;
    for(int b=1;b>suma1;b++)//sprawdzamy dzielniki sumy1
    {
    if(suma1%b==0)
    {
    suma2+=b;
    if (suma1==suma2) cout<<suma1<<" "<<suma2<<endl;
}}}}}

          
system("pause");
return 0;    
}

Mógłby ktoś ogarnięty w temacie poinstruować mnie co i jak?

[schleswig]

Pewnie da się napisać tysiąc razy lepiej i wydajniej, ale działa:

Kod: Zaznacz cały

#include <cstdio>

using namespace std;

int sumaDzielnikow(int n)
{
    int suma = 0;

    for(int i=1; 2*i<=n; i++)
        if(n%i == 0)
            suma += i;

    return suma;
}

int main()
{
    int zakres;

    scanf("%d", &zakres);

    for(int i=1; i<=zakres; i++)
    {
        int tmpSuma = sumaDzielnikow(i);

        for(int j=1; j<=zakres; j++)
        {
            int x=sumaDzielnikow(j);

            if((x == i) && (j == tmpSuma) && (i != j))
                printf("%d %d
", i, j);
        }
    }

    return 0;
}

Zadanie dla Ciebie: spraw, żeby nie wypisywały się dwa razy te same pary.

[Xitami]

tak jak to chciałeś zapisać powinno wyglądać tak:

Kod: Zaznacz cały

#include<iostream>
#include<cstdlib>
using namespace std;

int main() {
	int n, suma1, suma2; //2*było =0
	cin >> n;
    
	for( int a=1; a<=n; a++ )  //było ;a<n-1;
	{
		suma1= 0; // tego nie było
		for( int e=1; e<a; e++ ) 
			if( a%e==0 )
				suma1 += e;
		suma2= 0;
		for( int b=1; b<suma1; b++ )
			if( suma1%b == 0 )
				suma2 += b;
		if( a==suma2 ) //było sum1==sum2
			cout << a << " " << suma1 << endl;  // suma1 suma2
	}
	system("pause");
	return 0;    
}

na początek zapomnij o klamerkach, rób wcięcia, wtedy zobaczysz gdzie potrzebne są klamerki
Ładniej zrobił to schleswig
ale, funkcję sumaDzielnikow() zrobiłbym inaczej

Kod: Zaznacz cały

int sumdiv(int n){
	int i, sd=1;
	for( i=2; i*i<n; i++ )
		if( n%i==0 )
			sd += i + n/i;
	if( i*i==n ) return sd+i;
	else return sd;}

potrafi być tysiące razy szybsza
ale,...
program da się napisać chyba jeszcze lepiej

[Krzychu25]

No to mam tak, ale nie mogę wykombinować jak suma1 wyeliminować z następnej pętelki, żeby się nie wyświetlały podwójnie. Miałem tylko jedną lekcje o pętlach, bo 3 następne przepadły, a tu takie zadanie :/

Kod: Zaznacz cały

#include<iostream>
#include<cstdlib>
using namespace std;

int main() {
   int n, suma1, suma2;
   cin >> n;
    
   for( int a=1; a<=n; a++ ) 
   {
      suma1= 0;
      for( int e=1; e<a; e++ ) 
         if( a%e==0 )
            suma1 += e;
      suma2= 0;
      for( int b=1; b<suma1; b++ )
         if( suma1%b == 0)
            suma2 += b;
      if( a==suma2&&suma1!=suma2) //dodałem warunek
         cout << a << " " << suma1 << endl;  
   }
   system("pause");
   return 0;    
}

[Xitami]

przyjmij umowę, pierwsza musi być większa od drugiej, i już

tak jak radził schleswig to dobry zwyczaj, dwa razy (lub więcej) robisz to samo (szukasz sumy dzielników dwu liczb) zamknij to w funkcji (czasem robi się coś raz i też warto)

[Krzychu25]

Właśnie przed chwilą to zauważyłem. Dziękuję wszystkim za pomoc

[Xitami]

Porównanie szybkości dwu funkcji szukających sumy dzielników, czas w sekundach ()
\(\displaystyle{ \begin{tabular}{|r|r|r|}
\hline
n & sumaDzielnikow & sdiv\\
\hline
10 000 & 0,34 & 0,01 \\
20 000 & 1,41 & 0,05 \\
30 000 & 3,22 & 0,08 \\
315 000 & ??? & 3,21 \\ \hline
\end{tabular}}\)
w podobnym czasie jedna doszła do 30'000 druga do 315'000, podpierając się tablicą długości n+1 można w tym samym czasie doliczyć do 415'000.
Na ostatni zakres sumaDzielników potrzebuje (na moje oko) prawie godziny
Ładnie widać, że podwojenie zakresu powoduje, że czas rośnie czterokrotnie.
potrojenie, wydłuża czas 9 razy
czas rośnie z kwadratem n.
Dla sdiv() nie widać tego dobrz bo błąd pomiaru czasu zbyt wielki, ale czas jest proporcjonalny do pierwiastka z n