Sum of Squares Theorems

这个在Cryptography里有用，因为对于大的数找起来很难

Legendre's three square theorem: a positive integer can be expressed as a sum of 4 squares if and only if it is not of the form $4^a(8b+7)$ for integers $a,b$

Lagrange's Four Square Theorem / Bachet's conjecture: all positive integers can be expressed as a sum of 4 squares ($\forall n\in\mathbb{Z}^+,\exists a,b,c,d\in\mathbb{N}\text{ s.t. }n=a^2+b^2+c^2+d^2$)

一个用来算较小数的小代码

#include<bits/stdc++.h>
using namespace std;
int a,b,s[11111];
int main(){
	for(int i=0;i<50;i++){
		for(int j=i;j<50;j++){
			for(int k=j;k<50;k++){
				s[i*i+j*j+k*k]=1;
			}
		}
	}
	cin>>a>>b; // enter a range of values: [a,b)
	for(int i=a;i<b;i++){
		cout<<i<<" "<<s[i]<<endl;
		// 1 means expressible as the sum of 3 squares, 0 otherwise
	}
	return 0;
}