Liczby naturalne postaci n = m^2 + l^2

Napisz funkcję (lub program), która wypisuje wszystkie liczby naturalne z przedziału
〈1,n〉, które można przedstawić w postaci sumy kwadratów dwóch liczb naturalnych.
Złożoność czasowa i pamięciowa Twojego rozwiązania powinny być nie większe niż
O( n ).

Ma ktoś pomysł jak się za to zabrać? Z jakiej własności skorzystać, żeby to policzyć w O(n) ? Dzięki za odpowiedz.

for(m=0;mm<=n;++m)
for(l=m;ll+m*m<=n)

#include <stdio.h>

int main(){
	int x, n, m, l;
	int out = 0;
	scanf("%d", &x);
	for(int n = 2; n <= x; ++n){//lece sobie n razy
		out = 0;
		for( m=1 ; m*m <= n && !out; ++m){			
			for( l=m; l*l+m*m <= n; ++l ){
				if( l*l + m*m == n) { 
					printf("%d = %d^2 + %d^2\n", n,m,l); out = 1; break; //out zeby wyszlo jak znajdzie 5 = 1^2 + 2^2, a nie szukalo dalej 5 = 2^2 + 1^1
				}
			}
		}
	}
	//just for science( żeby wynik zobaczyć :)
	scanf("%d", &x);
}

Że niby tak? Ale jak udowodnić, że złożoność jest O(n)? W ogóle jest O(n)?

Złożoność algorytmu podanego przez @MarekR22 niestety jest O(n^2).

int n=...;
int p=0,k=sqrt(n+1); // n+1 aby nie wpaść na zaokrągleniach
while(p<=k)
  {
   int sum=p*p+k*k;
   if(sum>n) --k;
   else if(sum<n) ++p;
   else printf("%d = %d^2 + %d^2\n", n,p++,k--);
  }

Złożoność O(sqrt(n)), czyli mniejsza niż O(n).

ha..., te moje pętle można jeszcze poprawić :) :

for(m=0;m*m*2<=n;++m)
for(l=m;l*l+m*m<=n;++l)

Moje też można mocno przyśpieszyć:

int p=0,pp=0,k=sqrt(n+1),kk=k*k; // n+1 aby nie wpaść na zaokrągleniach
while(p<=k)
  {
   int sum=pp+kk;
   if(sum>n) pp=(--p)*p;
   else if(sum<n) kk=(++k)*k;
   else printf("%d = %d^2 + %d^2\n", n,p,k);
  }

Zrobione w ramach zabawy:
http://ideone.com/tiCwOK

Złożoność: O(n) = c.a. sqrt(n) * sqrt(n -1) => poniżej O(n)

Podaje też tutaj bo tam może zniknąć:

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int n = 100;
    int limit1 = sqrt(n);

    cout << "n: " << n << endl;
    cout << "Limit-1: " << limit1 << endl;

    for(int i=1; i <= limit1; i++ )
    {
      int limit2 = sqrt(n - i*i);
      for(int j = 1; j <= limit2; j++)
        cout << i << ", " << j << endl;
    }  
    
    return 0;
}

Edit:
Po dodaniu wyświetlania szukanych liczb:

http://ideone.com/D7r3Ek

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main() {
        int n = 100;
    int limit1 = sqrt(n);
 
    cout << "n: " << n << endl;
    cout << "Limit-1: " << limit1 << endl;
 
    for(int i=1; i <= limit1; i++ )
    {
      int limit2 = sqrt(n - i*i);
      for(int j = 1; j <= limit2; j++)
        cout << (i*i + j*j) << " = "<< i << "^2 + " << j << "^2"<< endl;
    }  
    
        return 0;
}

@vpiotr, ale na podstawie twojego pomysłu zrobiłem algorytm o złożoności O(sqrt(N)):

   int h=n>>1;
   for(int p=0,pp=0;pp<=h;++p,pp=p*p)
     {
      int mx=(int)sqrt(n-pp)+1;
      for(int k=mx-1;k<=mx;++k) if(pp+k*k==n) cout<<n<<" = "<<p<<"^2 + "<<k<<"^2"<<endl;
     }

Właściwie to teoretycznie powinno działać i to:

   int h=n>>1;
   for(int p=0,pp=0;pp<=h;++p,pp=p*p)
     {
      int k=sqrt(n-pp);
      if(pp+k*k==n) cout<<n<<" = "<<p<<"^2 + "<<k<<"^2"<<endl;
     }

Z tym że zaokrąglenia przy sqrt mogą spowodować że np sqrt(65001*65001) == 65000.99999999 i wtedy przeoczymy coś.

_13th_Dragon napisał(a):

@vpiotr, ale na podstawie twojego pomysłu zrobiłem algorytm o złożoności O(sqrt(N))

Zanim zaczniesz kogoś krytykować:
a) przeczytaj zadanie
b) przetestuj swoje rozwiązanie

Ad. (a) Liczba zero nie należy do poszukiwanych.
Ad. (b) Generujesz tylko jedną (bo 0^2 nie może być częścią pary) parę

Polecam serwis: http://ideone.com/

http://ideone.com/sBVpqi
http://ideone.com/jpo0qI