75 lines
1.8 KiB
C++
75 lines
1.8 KiB
C++
#include <iostream>
|
|
#include <cmath>
|
|
#include <chrono>
|
|
#define lmax 1500000
|
|
|
|
using namespace std;
|
|
typedef unsigned char byte;
|
|
|
|
inline int isqrt(int n) {
|
|
return (int)sqrt((float)n);
|
|
}
|
|
|
|
template<class T>
|
|
inline T gcd(T a, T b) {
|
|
while(b) {
|
|
auto t = a % b;
|
|
a = b;
|
|
b = t;
|
|
}
|
|
return a;
|
|
}
|
|
|
|
int main() {
|
|
byte arr[lmax+1];
|
|
auto start = chrono::system_clock::now();
|
|
|
|
for (int i = 0; i <= lmax; i++)
|
|
arr[i] = 0;
|
|
|
|
for (int length = 12; length <= lmax; length += 2)
|
|
for (int m = isqrt(length)/2+1; m <= isqrt(length/2); m++) {
|
|
if (length % (2*m) == 0)
|
|
{
|
|
int n = length / (2*m) - m;
|
|
if (n>0 && n < m && n%2!= m%2 && gcd(m,n) == 1)
|
|
arr[length]++;
|
|
}
|
|
}
|
|
|
|
auto middle = std::chrono::system_clock::now();
|
|
|
|
std::chrono::duration<double> elapsed_seconds = middle-start;
|
|
cout << "generating primitives took: " << elapsed_seconds.count() << endl;
|
|
|
|
|
|
for (int length = lmax; length >= 0; length--) {
|
|
int sqrtlen = isqrt(length);
|
|
for (int prev_length = 2; prev_length <= sqrtlen; prev_length++)
|
|
if (length % prev_length == 0) {
|
|
arr[length] += arr[prev_length];
|
|
arr[length] += arr[length/prev_length];
|
|
if (arr[length] > 1)
|
|
break;
|
|
}
|
|
}
|
|
auto end = std::chrono::system_clock::now();
|
|
|
|
elapsed_seconds = end-middle;
|
|
cout << "adding multiples took: " << elapsed_seconds.count() << endl;
|
|
|
|
|
|
int singles = 0;
|
|
|
|
for (int i = 0; i <= lmax; i++)
|
|
if (arr[i] == 1)
|
|
singles++;
|
|
|
|
for (int i = 0; i <= 60; i++)
|
|
if (arr[i] == 1)
|
|
cout << i << ", ";
|
|
cout << endl;
|
|
|
|
cout << singles;
|
|
return 0;
|
|
} |