详细分析看：http://www.cnblogs.com/devymex/archive/2010/08/14/1799713.html
要注意的是，p是指不满足x^2+y^2=z^2的数，这里的x、y、z并不要求是互质
#include <iostream> #include <cstring> #include <cmath> using namespace std; bool flag[1000001]; int N; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { while(cin >> N) { memset(flag, false, sizeof(flag)); int count = 0; int maxM = sqrt((float)N - 1); for(int m = 2; m <= maxM; m++) { int maxN = sqrt((float)N - m * m); maxN = maxN >= m ? m - 1 : maxN; for(int n = 1; n <= maxN; n++) { if(n % 2 != m % 2) { if(gcd(n, m) == 1) { count++; int a = m * m - n * n; int b = 2 * m * n; int c = m * m + n * n; for(int k = 0; c * k <= N; k++) flag[a * k] = flag[b * k] = flag[c * k] = true; } } } } cout << count << " "; count = 0; for(int i = 1; i <= N; i++) if(!flag[i]) count++; cout << count << endl; } return 0; }
