Tenemos el número n. Necesitamos encontrar si el número n puede ser representado por la suma de dos cuadrados.
Ejemplos:
Input : n = 17 Output : Yes 4^2 + 1^2 = 17 Input : n = 169 Output : Yes 5^2 + 12^2 = 169 Input : n = 24 Output : No
Enfoque de fuerza bruta – O(n)
Usamos dos bucles for que se ejecutan hasta la raíz cuadrada de n y cada vez encontramos si la suma del cuadrado de ambos números del bucle es igual a N. Si encontramos esa combinación, entonces imprimiremos Sí, de lo contrario No.
for i=1 to sqrt(n)
for j=i to sqrt(n)
if (i*i+j*j == n)
return true;
return false;
C++
// A brute force approach based implementation
// to find if a number can be written as sum
// of two squares.
#include <bits/stdc++.h>
using namespace std;
// function to check if there exist two
// numbers sum of whose squares is n.
bool sumSquare(int n)
{
for (long i = 1; i * i <= n; i++)
for (long j = 1; j * j <= n; j++)
if (i * i + j * j == n) {
cout << i << "^2 + "
<< j << "^2" << endl;
return true;
}
return false;
}
// driver Program
int main()
{
int n = 25;
if (sumSquare(n))
cout << "Yes";
else
cout << "No";
}
Java
// A brute force approach based implementation
// to find if a number can be written as sum
// of two squares.
class GFG {
// function to check if there exist two
// numbers sum of whose squares is n.
static boolean sumSquare(int n)
{
for (long i = 1; i * i <= n; i++)
for (long j = 1; j * j <= n; j++)
if (i * i + j * j == n) {
System.out.println(i + "^2 + "
+ j + "^2");
return true;
}
return false;
}
// driver Program
public static void main(String args[])
{
int n = 25;
if (sumSquare(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# A brute force approach based
# implementation to find if a number
# can be written as sum of two squares.
# function to check if there exist two
# numbers sum of whose squares is n.
def sumSquare( n) :
i = 1
while i * i <= n :
j = 1
while(j * j <= n) :
if (i * i + j * j == n) :
print(i, "^2 + ", j , "^2" )
return True
j = j + 1
i = i + 1
return False
# driver Program
n = 25
if (sumSquare(n)) :
print("Yes")
else :
print( "No")
# This code is contributed by Nikita Tiwari.
C#
// A brute force approach based
// implementation to find if a
// number can be written as sum
// of two squares
using System;
class GFG {
// function to check if there exist two
// numbers sum of whose squares is n
static bool sumSquare(int n)
{
for (long i = 1; i * i <= n; i++)
for (long j = 1; j * j <= n; j++)
if (i * i + j * j == n)
{
Console.Write(i + "^2 + "
+ j + "^2");
return true;
}
return false;
}
// Driver Code
public static void Main(String []args)
{
int n = 25;
if (sumSquare(n))
Console.Write("\nYes");
else
Console.Write("\nNo");
}
}
// This code is contributed by Smitha Dinesh Semwal.
PHP
<?php
// A brute force approach
// based implementation
// to find if a number
// can be written as sum
// of two squares.
// function to check
// if there exist two
// numbers sum of whose
// squares is n.
function sumSquare(int $n)
{
for ($i = 1; $i * $i <= $n; $i++)
for ( $j = 1; $j * $j <= $n; $j++)
if ($i * $i + $j * $j ==$n)
{
echo $i , "^2 + ",
$j , "^2" ;
return true;
}
return false;
}
// Driver Code
$n = 25;
if (sumSquare($n))
echo " \n","Yes";
else
echo "No";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A brute force approach based implementation
// to find if a number can be written as sum
// of two squares.
// function to check if there exist two
// numbers sum of whose squares is n.
function sumSquare(n) {
for (i = 1; i * i <= n; i++)
for (j = 1; j * j <= n; j++)
if (i * i + j * j == n) {
document.write(i + "^2 + " + j + "^2"+"<br/>");
return true;
}
return false;
}
// driver Program
var n = 25;
if (sumSquare(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by gauravrajput1
</script>
Producción:
3^2 + 4^2 Yes
También podemos tener este problema en O(sqrt(n))
Para resolver este problema en complejidad sqrt(n), usamos un hashmap donde almacenaremos los cuadrados de los números hasta sqrt(n), y cada vez buscaremos (n – sqrt(i)) en el hashmap si existe, luego devuelve Sí, de lo contrario, devuelve No.
unordered_map hashmap;
for i = 1 to sqrt(n)
hashmap[i*i]=1;
if (hashmap.find(N-i*i) != hashmap.end())
return true;
return false;
C++
// An efficient approach based implementation
// to find if a number can be written as sum
// of two squares.
#include <bits/stdc++.h>
using namespace std;
// function to check if there exist two
// numbers sum of whose squares is n.
bool sumSquare(int n)
{
unordered_map<int, int> s;
for (int i = 0; i * i <= n; ++i) {
// store square value in hashmap
s[i * i] = 1;
if (s.find(n - i * i) != s.end()) {
cout << sqrt(n - i * i) << "^2 + "
<< i << "^2" << endl;
return true;
}
}
return false;
}
// driver Program
int main()
{
int n = 169;
if (sumSquare(n))
cout << "Yes";
else
cout << "No";
}
Java
// An efficient approach based implementation
// to find if a number can be written as sum
// of two squares.
import java.util.*;
class GFG
{
// function to check if there exist two
// numbers sum of whose squares is n.
static boolean sumSquare(int n)
{
HashMap<Integer,
Integer> s = new HashMap<Integer,
Integer>();
for (int i = 0; i * i <= n; ++i)
{
// store square value in hashmap
s.put(i * i, 1);
if (s.containsKey(n - i * i))
{
System.out.println((int)Math.sqrt(n - i * i) +
"^2 + " + i + "^2");
return true;
}
}
return false;
}
// Driver Code
public static void main(String[] args)
{
int n = 169;
System.out.print(sumSquare(n) ?
"YES\n" : "NO\n");
}
}
// This code is contributed by Princi Singh
Python3
# An efficient approach based implementation
# to find if a number can be written as sum
# of two squares.
# function to check if there exist two
# numbers sum of whose squares is n.
def sumSquare(n):
s = dict()
for i in range(n):
if i * i > n:
break
# store square value in hashmap
s[i * i] = 1
if (n - i * i) in s.keys():
print((n - i * i)**(1 / 2),
"^2 +", i, "^2")
return True
return False
# Driver Code
n = 1
if n==1:
print('0^2 + 1^2')
elif (sumSquare(n)):
print("Yes")
else:
print("No")
# This code is contributed by Mohit Kumar
C#
// An efficient approach based implementation
// to find if a number can be written as sum
// of two squares.
using System;
using System.Collections.Generic;
class GFG
{
// function to check if there exist two
// numbers sum of whose squares is n.
static bool sumSquare(int n)
{
Dictionary<int, int> s = new Dictionary<int, int>();
for (int i = 0; i * i <= n; ++i)
{
// store square value in hashmap
s.Add(i * i, 1);
if (s.ContainsKey(n - i * i))
{
Console.WriteLine((int)Math.Sqrt(n - i * i) +
"^2 + " + i + "^2");
return true;
}
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
int n = 169;
Console.WriteLine(sumSquare(n) ?
"YES" : "NO");
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// An efficient approach based implementation
// to find if a number can be written as sum
// of two squares.
// function to check if there exist two
// numbers sum of whose squares is n.
function sumSquare(n)
{
let s = new Map();
for (let i = 0; i * i <= n; ++i){
// store square value in hashmap
s.set(i * i, 1);
if (s.has(n - i * i))
{
document.write(Math.sqrt(n - i * i) +
"^2 + " + i + "^2<br>");
return true;
}
}
return false;
}
// Driver Code
let n = 169;
document.write(sumSquare(n) ?
"YES<br>" : "NO<br>");
// This code is contributed by unknown2108
</script>
Producción :
5^2 + 12^2 Yes
También podemos este problema en O(sqrt(n)log n)
Este enfoque ha sido aportado por Sagar Shukla .
Enfoque de búsqueda binaria:
otro método para verificar si 
es un cuadrado perfecto es hacer uso de la búsqueda binaria. El método sigue siendo el mismo que el de una búsqueda binaria típica para encontrar un número. La única diferencia radica en que necesitamos encontrar un número entero medio en el rango ![[0, c - a^2]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-013442481d1ae8c4654c88f45b36d44f_l3.png "Rendered by QuickLaTeX.com")
tal que este número sea la raíz cuadrada de O en otras palabras, necesitamos encontrar un número entero medio en el rango ![[0, c - a^2]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-4ba1509f2564613358c42d79c2822329_l3.png "Rendered by QuickLaTeX.com")
tal que midxmid = 
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Check whether a number can be
// represented by sum of two squares using binary search.
#include<iostream>
#include<cmath>
using namespace std;
// Function for binary search.
bool binary_search(int num2, int se, int num)
{
int mid;
int ss=0;
while(ss<=se)
{
// Calculating mid.
mid=(ss+se)/2;
if ((pow(mid,2)+pow(num2,2))==num)
{
return true;
}
else if ((pow(mid,2)+pow(num2,2))>num)
{
se=mid-1;
}
else
{
ss=mid+1;
}
}
return false;
}
// Driver code
int main()
{
int rt;
int num=169;
rt=sqrt(num);
bool flag=false;
for (int i = rt; i >=0; --i)
{
if (binary_search(i,i,num))
{
flag=true;
break;
}
}
if (flag)
{
cout<<"true";
}
else cout<<"false";
return 0;
}
// This code is contributed by Dhruv Gupta
Java
// Java program for Check whether a number can be
// represented by sum of two squares using binary search.
import java.util.*;
import java.lang.*;
public class GfG {
public static boolean judgeSquareSum(int c)
{
// Iterating loop from 0 to c - a * a.
for (long a = 0; a * a <= c; a++) {
int b = c - (int)(a * a);
// If b is a square root of c - a * a
// then return true.
if (binary_search(0, b, b))
return true;
}
return false;
}
// Function for binary search.
public static boolean binary_search(long s, long e, int n)
{
// If lower limit exceeds upper limit.
if (s > e)
return false;
// Calculating mid.
long mid = s + (e - s) / 2;
if (mid * mid == n)
return true;
if (mid * mid > n)
return binary_search(s, mid - 1, n);
return binary_search(mid + 1, e, n);
}
// Driver function
public static void main(String argc[])
{
int c = 17;
System.out.println(judgeSquareSum(c));
}
}
Python3
# Python3 program for Check whether
# a number can be represented by
# sum of two squares using binary search.
def judgeSquareSum(c):
# Iterating loop from 0 to c - a * a.
a = 0;
while(a * a <= c):
b = c - int(a * a);
# If b is a square root of
# c - a * a then return true.
if (binary_search(0, b, b)):
return 1;
a+=1;
return 0;
# Function for binary search.
def binary_search(s, e, n):
# If lower limit exceeds
# upper limit.
if (s > e):
return 0;
# Calculating mid.
mid = s + int((e - s) / 2);
if (int(mid * mid) == n):
return 1;
if (int(mid * mid) > n):
return binary_search(s, mid - 1, n);
return binary_search(mid + 1, e, n);
# Driver Code
c = 17;
if(judgeSquareSum(c)):
print("true");
else:
print("false");
# This code is contributed by mits
C#
// C# program for Check whether a
// number can be represented by
// sum of two squares using
// binary search.
using System;
class GFG {
public static bool judgeSquareSum(int c)
{
// Iterating loop from 0 to c - a * a.
for (long a = 0; a * a <= c; a++)
{
int b = c - (int)(a * a);
// If b is a square root of c - a * a
// then return true.
if (binary_search(0, b, b))
return true;
}
return false;
}
// Function for binary search.
public static bool binary_search(long s,
long e, int n)
{
// If lower limit exceeds upper limit.
if (s > e)
return false;
// Calculating mid.
long mid = s + (e - s) / 2;
if (mid * mid == n)
return true;
if (mid * mid > n)
return binary_search(s, mid - 1, n);
return binary_search(mid + 1, e, n);
}
// Driver Code
public static void Main()
{
int c = 17;
Console.WriteLine(judgeSquareSum(c));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program for Check whether
// a number can be represented by
// sum of two squares using binary search.
function judgeSquareSum($c)
{
// Iterating loop from 0 to c - a * a.
for ($a = 0; $a * $a <= $c; $a++)
{
$b = $c - intval($a * $a);
// If b is a square root of
// c - a * a then return true.
if (binary_search(0, $b, $b))
return 1;
}
return 0;
}
// Function for binary search.
function binary_search($s, $e, $n)
{
// If lower limit exceeds
// upper limit.
if ($s > $e)
return 0;
// Calculating mid.
$mid = $s + intval(($e - $s) / 2);
if (intval($mid * $mid) == $n)
return 1;
if (intval($mid * $mid) > $n)
return binary_search($s, $mid - 1, $n);
return binary_search($mid + 1, $e, $n);
}
// Driver Code
$c = 17;
if(judgeSquareSum($c))
echo "true";
else
echo "false";
// This code is contributed by Sam007
?>
Javascript
<script>
// javascript program for Check whether a number can be
// represented by sum of two squares using binary search.
function judgeSquareSum(c) {
// Iterating loop from 0 to c - a * a.
for (a = 0; a * a <= c; a++) {
var b = c - parseInt( (a * a));
// If b is a square root of c - a * a
// then return true.
if (binary_search(0, b, b))
return true;
}
return false;
}
// Function for binary search.
function binary_search(s , e , n) {
// If lower limit exceeds upper limit.
if (s > e)
return false;
// Calculating mid.
var mid = s + parseInt((e - s) / 2);
if (mid * mid == n)
return true;
if (mid * mid > n)
return binary_search(s, mid - 1, n);
return binary_search(mid + 1, e, n);
}
// Driver function
var c = 17;
document.write(judgeSquareSum(c));
// This code is contributed by Rajput-Ji
</script>
Producción:
true
Complejidad del tiempo : O(sqrt(c)log(c))
Este enfoque ha sido aportado por Sagar Shukla .
Enfoque del teorema de Fermat:
Este enfoque se basa en la siguiente afirmación, que se basa en el teorema de Fermat:
“Cualquier número positivo n se puede expresar como una suma de dos cuadrados si y solo si se produce la descomposición en factores primos de n , cada primo de la forma (4k + 3) un número par de veces.”
Haciendo uso del teorema anterior, podemos averiguar directamente si el número dado n se puede expresar como una suma de dos cuadrados.
Para hacerlo, simplemente encontramos todos los factores primos del número dado n, que podría variar ![[2,\sqrt{n}]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-a7cfc5f79b18419149ff8ffb09758e3c_l3.png "Rendered by QuickLaTeX.com")
junto con la cuenta de esos factores, mediante división repetida. Si en cualquier paso, descubrimos que el número de ocurrencias de cualquier factor primo de la forma (4k + 3) ocurre un número impar de veces, podemos devolver un valor falso.
Si n mismo es un número primo, no será divisible por ninguno de los primos en ![[2,\sqrt{n}]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-395f7884e3e47b4be7c36af0e588da42_l3.png "Rendered by QuickLaTeX.com")
. Por lo tanto, debemos verificar si n se puede expresar en la forma de (4k + 3). Si es así, necesitamos devolver un valor falso, lo que indica que este primo ocurre un número impar (1) de veces.
De lo contrario, podemos devolver el valor verdadero.
C++
// Check whether a number can be represented
// by sum of two squares using Fermat Theorem.
#include<bits/stdc++.h>
using namespace std;
bool judgeSquareSum(int n)
{
for (int i = 2;
i * i <= n; i++)
{
int count = 0;
if (n % i == 0)
{
// Count all the prime factors.
while (n % i == 0)
{
count++;
n /= i;
}
// Ifany prime factor of the form
// (4k+3)(4k+3) occurs an odd
// number of times.
if (i % 4 == 3 && count % 2 != 0)
return false;
}
}
// If n itself is a x prime number and
// can be expressed in the form of
// 4k + 3 we return false.
return n % 4 != 3;
}
// Driver Code
int main()
{
int n = 17;
if(judgeSquareSum(n))
cout << "Yes";
else
cout << "No";
}
// This code is contributed by
// prabhat kumar singh
Java
// Java program to Check whether a number
// can be represented by sum of two
// squares using Fermat Theorem.
import java.util.*;
import java.lang.*;
class GFG
{
public static boolean judgeSquareSum(int n)
{
for (int i = 2; i * i <= n; i++)
{
int count = 0;
if (n % i == 0)
{
// Count all the prime factors.
while (n % i == 0)
{
count++;
n /= i;
}
// Ifany prime factor of the form
// (4k+3)(4k+3) occurs an odd
// number of times.
if (i % 4 == 3 && count % 2 != 0)
return false;
}
}
// If n itself is a prime number and can
// be expressed in the form of 4k + 3
// we return false.
return n % 4 != 3;
}
// Driver Code
public static void main(String argc[])
{
int n = 17;
if(judgeSquareSum(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Check whether a number can be represented
# by sum of two squares using Fermat Theorem.
def judgeSquareSum(n):
i = 2;
while (i * i <= n):
count = 0;
if (n % i == 0):
# Count all the prime factors.
while (n % i == 0):
count += 1;
n = int(n / i);
# Ifany prime factor of the
# form (4k+3)(4k+3) occurs
# an odd number of times.
if (i % 4 == 3 and count % 2 != 0):
return False;
i += 1;
# If n itself is a x prime number and
# can be expressed in the form of 4k + 3
# we return false.
return n % 4 != 3;
# Driver Code
n = 17;
if(judgeSquareSum(n)):
print("Yes");
else:
print("No");
# This code is contributed by mits
C#
// C# program to Check whether a number
// can be represented by sum of two
// squares using Fermat Theorem.
using System;
class GFG
{
public static bool judgeSquareSum(int n)
{
for (int i = 2; i * i <= n; i++)
{
int count = 0;
if (n % i == 0)
{
// Count all the prime factors.
while (n % i == 0)
{
count++;
n /= i;
}
// If any prime factor of the
// form (4k+3)(4k+3) occurs an
// odd number of times.
if (i % 4 == 3 && count % 2 != 0)
return false;
}
}
// If n itself is a prime number and
// can be expressed in the form of
// 4k + 3 we return false.
return n % 4 != 3;
}
// Driver Code
static public void Main ()
{
int n = 17;
if(judgeSquareSum(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed
// by akt_mit
PHP
<?php
// Check whether a number can be represented
// by sum of two squares using Fermat Theorem.
function judgeSquareSum($n)
{
for ($i = 2; $i * $i <= $n; $i++)
{
$count = 0;
if ($n % $i == 0)
{
// Count all the
// prime factors.
while ($n % $i == 0)
{
$count++;
$n = (int) $n / $i;
}
// Ifany prime factor of the
// form (4k+3)(4k+3) occurs
// an odd number of times.
if ($i % 4 == 3 &&
$count % 2 != 0)
return false;
}
}
// If n itself is a x prime number and
// can be expressed in the form of 4k + 3
// we return false.
return $n % 4 != 3;
}
// Driver Code
$n = 17;
if(judgeSquareSum($n))
echo "Yes";
else
echo "No";
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to Check whether a number
// can be represented by sum of two
// squares using Fermat Theorem.
function judgeSquareSum(n)
{
for(i = 2; i * i <= n; i++)
{
var count = 0;
if (n % i == 0)
{
// Count all the prime factors.
while (n % i == 0)
{
count++;
n = parseInt(n / i);
}
// If any prime factor of the form
// (4k+3)(4k+3) occurs an odd
// number of times.
if (i % 4 == 3 && count % 2 != 0)
return false;
}
}
// If n itself is a prime number and can
// be expressed in the form of 4k + 3
// we return false.
return n % 4 != 3;
}
// Driver Code
var n = 17;
if (judgeSquareSum(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by Rajput-Ji
</script>
Producción :
Yes
Publicación traducida automáticamente
Artículo escrito por niteesh_Kr y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA