lean grove
cheeze numbers are integers of the form 3 * p^n where p is an odd prime and n is a natural number. Determine the sum of the first 2019 cheeze numbers.
Examples of cheeze numbers:
- 3 (3 * 7^0)
- 15 (3 * 5^1)
- 363 (3 * 11^2)
The first 9 cheeze numbers are as follows:
3 9 15 21 27 33 39 51 57
Answer: ||47960571||
dry hornet
||it's just dividing the number by 3 then finding the nth root till the root is odd prime isn't it||
lean grove
||that's gonna take forever ||
lean grove
Solution:
||
#include <iostream>
#include <queue>
using namespace std;
using ii = pair<int, int>;
// Generate primes up to one million
constexpr int MAX_PRIME = 1000000;
// Generate odd primes with sieve of eratosthenes
vector<int> generate_odd_primes() {
vector<int> primes;
vector<bool> sieve(MAX_PRIME, true);
sieve[0] = false;
sieve[1] = false;
int i = 2;
while (i < MAX_PRIME) {
if (!sieve[i]) {
i++;
continue;
}
// We want odd primes only, 2 isn't odd
if (i != 2) primes.push_back(i);
for (int j = i + i; j < MAX_PRIME; j += i) sieve[j] = false;
i++;
}
return primes;
}
// Generate 2019 cheeze numbers
constexpr int N = 2019;
int main() {
vector<int> primes = generate_odd_primes();
// A min heap for to determine the next prime power (p^n)
// 3, 5, 7, 9, 11, 13, 17, 19, 23, 25, 27, 29, ...
priority_queue<ii, vector<ii>, greater<ii>> pq;
for (int p : primes) pq.push({ p, p });
// The first cheeze number is 3
int sum = 3;
// We just need to find the next (N - 1) cheeze numbers
// By multiplying whatever is in the priority queue by 3
// Because cheeze number is 3 * p^n
for (int i = 0; i < N - 1; i++) {
// Retrieve the next prime power
// x -> current value of prime power
// y -> what the prime number was
auto [x, y] = pq.top();
// Remove the current prime power
pq.pop();
// Generate the next prime power
pq.push({ x * y, y });
// cheeze number = x * 3
// Add it to the sum
sum += x * 3;
}
cout << sum << endl;
}
||
dry hornet
function isPrime(n){if(n<=1)return!1;for(let i=2;i<=Math.sqrt(n);i++)if(n%i==0)return!1;return!0}function getCheeseNumber(p,n){return 3*Math.pow(p,n)}let total=0,count=0,p=3,n=0;while(count<2019){const cheeseNumber=getCheeseNumber(p,n);total+=cheeseNumber,count++,n++,n>0&&!isPrime(p)&&(do{p+=2}while(!isPrime(p)),n=0)}console.log(total);```