Maximal Prime Score M(k, n): choose a_i in [0, k) with sum(a_i) divisible by k, maximize sum(p(a_i)). Strategy: start from all a_i = k-1, find minimal reduction r = (-n) % k, then minimize prime-score loss via unbounded knapsack.
# Project Euler 874
# Maximal Prime Score
# M(k, n): choose a_i in [0, k) with sum(a_i) divisible by k, maximize sum(p(a_i)).
# Strategy: start from all a_i = k-1, find minimal reduction r = (-n) % k,
# then minimize prime-score loss via unbounded knapsack.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
function memset(p: ptr<void>, c: i32, n: i64) -> ptr<void>
function log(x: f64) -> f64
}
function first_n_primes(n: i64) -> ptr<i32> {
if n <= 0 { return null }
let mut limit: i64 = 0
if n < 6 {
limit = 15
} else {
let nn: f64 = n as f64
limit = (nn * (log(nn) + log(log(nn))) + 10.0) as i64
}
let mut found: bool = false
let mut primes: ptr<i32> = null
while !found {
let sieve: ptr<i8> = malloc(limit + 1)
memset(sieve, 1, limit + 1)
sieve[0] = 0
sieve[1] = 0
let mut i: i64 = 2
while i * i <= limit {
if sieve[i] != 0 {
let mut j: i64 = i * i
while j <= limit {
sieve[j] = 0
j = j + i
}
}
i = i + 1
}
let mut count: i64 = 0
i = 2
while i <= limit {
if sieve[i] != 0 { count = count + 1 }
i = i + 1
}
if count >= n {
primes = malloc(n * 4)
let mut idx: i64 = 0
i = 2
while i <= limit && idx < n {
if sieve[i] != 0 {
primes[idx] = i as i32
idx = idx + 1
}
i = i + 1
}
free(sieve)
found = true
} else {
free(sieve)
limit = limit * 2
}
}
return primes
}
function min_prime_loss(primes: ptr<i32>, k: i64, reduction: i64) -> i64 {
if reduction == 0 { return 0 }
let m: i64 = k - 1
let top: i64 = primes[m] as i64
# loss[d] = top - primes[m - d] for d = 1..reduction
let loss: ptr<i64> = malloc((reduction + 1) * 8)
let mut d: i64 = 1
while d <= reduction {
loss[d] = top - (primes[m - d] as i64)
d = d + 1
}
# dp[s] = minimal loss to achieve sum s
let INF: i64 = 1000000000000000000
let dp: ptr<i64> = malloc((reduction + 1) * 8)
dp[0] = 0
let mut s: i64 = 1
while s <= reduction {
dp[s] = INF
s = s + 1
}
d = 1
while d <= reduction {
let c: i64 = loss[d]
s = d
while s <= reduction {
let cand: i64 = dp[s - d] + c
if cand < dp[s] {
dp[s] = cand
}
s = s + 1
}
d = d + 1
}
let result: i64 = dp[reduction]
free(loss)
free(dp)
return result
}
function maximal_prime_score(k: i64, n: i64, primes: ptr<i32>) -> i64 {
if k == 1 { return n * 2 }
let top: i64 = primes[k - 1] as i64
# r = ((-n) % k + k) % k
let mut r: i64 = (0 - n) % k
if r < 0 { r = r + k }
let loss: i64 = min_prime_loss(primes, k, r)
return n * top - loss
}
function main() -> i32 {
let k: i64 = 7000
let primes_7001: ptr<i32> = first_n_primes(k + 1)
let n: i64 = primes_7001[k] as i64
let ans: i64 = maximal_prime_score(k, n, primes_7001)
printf("%lld\n", ans)
free(primes_7001)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int32_t* first_n_primes_i64(int64_t n);
int64_t min_prime_loss_ptr_i32_i64_i64(int32_t* primes, int64_t k, int64_t reduction);
int64_t maximal_prime_score_i64_i64_ptr_i32(int64_t k, int64_t n, int32_t* primes);
int32_t main(void);
int32_t* first_n_primes_i64(int64_t n) {
if (n <= 0) {
return NULL;
}
int64_t limit = 0;
if (n < 6) {
limit = 15;
} else {
double nn = ((double)(n));
limit = ((int64_t)(((nn * (log(nn) + log(log(nn)))) + 10.0)));
}
bool found = 0;
int32_t* primes = (int32_t*)(NULL);
while ((!(found))) {
int8_t* sieve = (int8_t*)(malloc((limit + 1)));
memset(sieve, 1, (limit + 1));
sieve[0] = 0;
sieve[1] = 0;
int64_t i = 2;
while ((i * i) <= limit) {
if (sieve[i] != 0) {
int64_t j = (i * i);
while (j <= limit) {
sieve[j] = 0;
j = (j + i);
}
}
i = (i + 1);
}
int64_t count = 0;
i = 2;
while (i <= limit) {
if (sieve[i] != 0) {
count = (count + 1);
}
i = (i + 1);
}
if (count >= n) {
primes = malloc((n * 4));
int64_t idx = 0;
i = 2;
while ((i <= limit && idx < n)) {
if (sieve[i] != 0) {
primes[idx] = ((int32_t)(i));
idx = (idx + 1);
}
i = (i + 1);
}
free(sieve);
found = 1;
} else {
free(sieve);
limit = (limit * 2);
}
}
return primes;
}
int64_t min_prime_loss_ptr_i32_i64_i64(int32_t* primes, int64_t k, int64_t reduction) {
if (reduction == 0) {
return 0;
}
int64_t m = (k - 1);
int64_t top = ((int64_t)(primes[m]));
int64_t* loss = (int64_t*)(malloc(((reduction + 1) * 8)));
int64_t d = 1;
while (d <= reduction) {
loss[d] = (top - ((int64_t)(primes[(m - d)])));
d = (d + 1);
}
int64_t INF = 1000000000000000000;
int64_t* dp = (int64_t*)(malloc(((reduction + 1) * 8)));
dp[0] = 0;
int64_t s = 1;
while (s <= reduction) {
dp[s] = INF;
s = (s + 1);
}
d = 1;
while (d <= reduction) {
int64_t c = loss[d];
s = d;
while (s <= reduction) {
int64_t cand = (dp[(s - d)] + c);
if (cand < dp[s]) {
dp[s] = cand;
}
s = (s + 1);
}
d = (d + 1);
}
int64_t result = dp[reduction];
free(loss);
free(dp);
return result;
}
int64_t maximal_prime_score_i64_i64_ptr_i32(int64_t k, int64_t n, int32_t* primes) {
if (k == 1) {
return (n * 2);
}
int64_t top = ((int64_t)(primes[(k - 1)]));
int64_t r = FLOW_CHECKED_MOD(((0 - n)), (k));
if (r < 0) {
r = (r + k);
}
int64_t loss = min_prime_loss_ptr_i32_i64_i64(primes, k, r);
return ((n * top) - loss);
}
int32_t main(void) {
int64_t k = 7000;
int32_t* primes_7001 = (int32_t*)(first_n_primes_i64((k + 1)));
int64_t n = ((int64_t)(primes_7001[k]));
int64_t ans = maximal_prime_score_i64_i64_ptr_i32(k, n, primes_7001);
printf("%lld\n", ans);
free(primes_7001);
return 0;
}