88 lines
1.9 KiB
C++
88 lines
1.9 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <cmath>
|
|
#include <chrono>
|
|
typedef long long int Int;
|
|
|
|
using namespace std;
|
|
|
|
vector<Int> primes;
|
|
|
|
void generatePrimes() {
|
|
primes.push_back(2);
|
|
primes.push_back(3);
|
|
for (int i = 5; i < 1000000; i += 2) {
|
|
bool isPrime = true;
|
|
for (auto p : primes) {
|
|
if ((int)p*(int)p > i)
|
|
break;
|
|
if (i % (int)p == 0) {
|
|
isPrime = false;
|
|
break;
|
|
}
|
|
}
|
|
if (isPrime)
|
|
primes.push_back((Int)i);
|
|
}
|
|
}
|
|
|
|
bool check420LatticePoints(Int n) {
|
|
int latticePoints = 1;
|
|
|
|
for (auto p : primes) {
|
|
if (p*p > n)
|
|
p = n;
|
|
|
|
int multiplicity = 0;
|
|
|
|
while (n % p == 0) {
|
|
multiplicity++;
|
|
n /= p;
|
|
}
|
|
|
|
if (multiplicity > 0 && p % 4 == 1) {
|
|
latticePoints *= 2*multiplicity+1;
|
|
|
|
if (latticePoints == 105)
|
|
return true;
|
|
|
|
if (105 % latticePoints != 0)
|
|
return false;
|
|
}
|
|
|
|
if (n==1)
|
|
return false;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
int main() {
|
|
Int max;
|
|
cout << "N = ";
|
|
cin >> max;
|
|
|
|
auto start = chrono::system_clock::now();
|
|
|
|
generatePrimes();
|
|
|
|
auto middle = std::chrono::system_clock::now();
|
|
|
|
std::chrono::duration<double> elapsed_seconds = middle-start;
|
|
cout << "generating primes took: " << elapsed_seconds.count() << endl;
|
|
|
|
Int count = 0, sum = 0;
|
|
for (Int n = 10; n < max; n++) {
|
|
if (check420LatticePoints(n)) {
|
|
sum += n;
|
|
count++;
|
|
}
|
|
}
|
|
auto end = std::chrono::system_clock::now();
|
|
|
|
elapsed_seconds = end-middle;
|
|
cout << "finding 420s took: " << elapsed_seconds.count() << endl << endl;
|
|
|
|
cout << "sum: " << sum << ", total: " << count;
|
|
return 0;
|
|
}
|