# Project Euler 927
# Prime-ary Tree: R(10^7) = sum of m in S (intersection of S_p) with m <= 10^7.
# Pure Flow port of the native C solver.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
function sqrt(x: f64) -> f64
}
const LIMIT: i64 = 10000000
let mut is_comp: ptr<i8> = null as ptr<i8>
let mut primes_arr: ptr<i32> = null as ptr<i32>
let mut num_primes: i32 = 0
function mod_pow_i64(a0: i64, e0: i64, mod: i64) -> i64 {
let mut r: i64 = 1 % mod
let mut a: i64 = a0 % mod
if a < 0 { a = a + mod }
let mut e: i64 = e0
while e > 0 {
if (e & 1) != 0 { r = r * a % mod }
a = a * a % mod
e = e >> 1
}
return r
}
function hits_zero_mod_prime(q: i64, k: i64) -> i32 {
if q == 2 { return 1 }
if (q - 1) % k != 0 { return 1 }
let mut tortoise: i64 = 1
let mut hare: i64 = (1 + mod_pow_i64(1, k, q)) % q
if hare == 0 { return 1 }
let mut power: i64 = 1
let mut lam: i64 = 1
while tortoise != hare {
if hare == 0 { return 1 }
if power == lam {
tortoise = hare
power = power << 1
lam = 0
}
hare = (1 + mod_pow_i64(hare, k, q)) % q
lam = lam + 1
}
if hare == 0 { return 1 }
return 0
}
function hits_zero_mod_prime_k2(q: i64) -> i32 {
if q == 2 { return 1 }
let mut tortoise: i64 = 1
let mut hare: i64 = (1 + 1) % q
if hare == 0 { return 1 }
let mut power: i64 = 1
let mut lam: i64 = 1
while tortoise != hare {
if hare == 0 { return 1 }
if power == lam {
tortoise = hare
power = power << 1
lam = 0
}
hare = (hare * hare + 1) % q
lam = lam + 1
}
if hare == 0 { return 1 }
return 0
}
function sieve_upto(n: i64) -> void {
is_comp = calloc(n + 1, 1) as ptr<i8>
is_comp[0] = 1
is_comp[1] = 1
let lim: i64 = sqrt(n as f64) as i64
let mut i: i64 = 2
while i <= lim {
if is_comp[i] == 0 {
let mut j: i64 = i * i
while j <= n {
is_comp[j] = 1
j = j + i
}
}
i = i + 1
}
let mut cnt: i64 = 0
i = 2
while i <= n {
if is_comp[i] == 0 { cnt = cnt + 1 }
i = i + 1
}
primes_arr = malloc(cnt * 4) as ptr<i32>
num_primes = 0
i = 2
while i <= n {
if is_comp[i] == 0 {
primes_arr[num_primes] = i as i32
num_primes = num_primes + 1
}
i = i + 1
}
}
function prime_factors_unique(n: i32, out: ptr<i32>) -> i32 {
let mut x: i32 = n
let mut cnt: i32 = 0
let mut i: i32 = 0
while i < num_primes {
let p: i32 = primes_arr[i]
if (p as i64) * (p as i64) > (x as i64) { break }
if x % p == 0 {
out[cnt] = p
cnt = cnt + 1
while x % p == 0 { x = x / p }
}
i = i + 1
}
if x > 1 {
out[cnt] = x
cnt = cnt + 1
}
return cnt
}
function main() -> i32 {
sieve_upto(LIMIT)
# Find good primes
let good_primes: ptr<i32> = malloc((num_primes as i64) * 4) as ptr<i32>
let mut num_good: i32 = 0
let factors_buf: ptr<i32> = malloc(32 * 4) as ptr<i32>
let mut pi: i32 = 0
while pi < num_primes {
let q: i32 = primes_arr[pi]
if q == 2 {
good_primes[num_good] = q
num_good = num_good + 1
} else {
if (q & 3) == 1 {
if hits_zero_mod_prime_k2(q as i64) != 0 {
let nf: i32 = prime_factors_unique(q - 1, factors_buf)
let mut ok: i32 = 1
let mut fi: i32 = 0
while fi < nf {
let p: i32 = factors_buf[fi]
if p != 2 {
if hits_zero_mod_prime(q as i64, p as i64) == 0 {
ok = 0
}
}
if ok == 0 { break }
fi = fi + 1
}
if ok != 0 {
good_primes[num_good] = q
num_good = num_good + 1
}
}
}
}
pi = pi + 1
}
# Sum of squarefree products <= LIMIT
let mut cap: i64 = 1 << 20
let mut prods: ptr<i32> = malloc(cap * 4) as ptr<i32>
let mut len: i64 = 1
prods[0] = 1
let mut pidx: i32 = 0
while pidx < num_good {
let p: i32 = good_primes[pidx]
let base_len: i64 = len
let mut i: i64 = 0
while i < base_len {
let v: i64 = (prods[i] as i64) * (p as i64)
if v <= LIMIT {
if len >= cap {
let new_cap: i64 = cap << 1
let newp: ptr<i32> = malloc(new_cap * 4) as ptr<i32>
memcpy(newp as ptr<void>, prods as ptr<void>, cap * 4)
free(prods)
prods = newp
cap = new_cap
}
prods[len] = v as i32
len = len + 1
}
i = i + 1
}
pidx = pidx + 1
}
let mut total: i64 = 0
let mut i: i64 = 0
while i < len {
total = total + (prods[i] as i64)
i = i + 1
}
printf("%lld\n", total)
free(is_comp)
free(primes_arr)
free(good_primes)
free(factors_buf)
free(prods)
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; }
int64_t mod_pow_i64_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod);
int32_t hits_zero_mod_prime_i64_i64(int64_t q, int64_t k);
int32_t hits_zero_mod_prime_k2_i64(int64_t q);
void sieve_upto_i64(int64_t n);
int32_t prime_factors_unique_i32_ptr_i32(int32_t n, int32_t* out);
int32_t main(void);
static const int64_t LIMIT = 10000000;
/* Module statics */
static int8_t* is_comp = ((int8_t*)(NULL));
static int32_t* primes_arr = ((int32_t*)(NULL));
static int32_t num_primes = 0;
int64_t mod_pow_i64_i64_i64_i64(int64_t a0, int64_t e0, int64_t mod) {
int64_t r = FLOW_CHECKED_MOD((1), (mod));
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
if (a < 0) {
a = (a + mod);
}
int64_t e = e0;
while (e > 0) {
if ((e & 1) != 0) {
r = FLOW_CHECKED_MOD(((r * a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * a)), (mod));
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int32_t hits_zero_mod_prime_i64_i64(int64_t q, int64_t k) {
if (q == 2) {
return 1;
}
if (FLOW_CHECKED_MOD(((q - 1)), (k)) != 0) {
return 1;
}
int64_t tortoise = 1;
int64_t hare = FLOW_CHECKED_MOD(((1 + mod_pow_i64_i64_i64_i64(1, k, q))), (q));
if (hare == 0) {
return 1;
}
int64_t power = 1;
int64_t lam = 1;
while (tortoise != hare) {
if (hare == 0) {
return 1;
}
if (power == lam) {
tortoise = hare;
power = FLOW_CHECKED_SHL((power), (1));
lam = 0;
}
hare = FLOW_CHECKED_MOD(((1 + mod_pow_i64_i64_i64_i64(hare, k, q))), (q));
lam = (lam + 1);
}
if (hare == 0) {
return 1;
}
return 0;
}
int32_t hits_zero_mod_prime_k2_i64(int64_t q) {
if (q == 2) {
return 1;
}
int64_t tortoise = 1;
int64_t hare = FLOW_CHECKED_MOD(((1 + 1)), (q));
if (hare == 0) {
return 1;
}
int64_t power = 1;
int64_t lam = 1;
while (tortoise != hare) {
if (hare == 0) {
return 1;
}
if (power == lam) {
tortoise = hare;
power = FLOW_CHECKED_SHL((power), (1));
lam = 0;
}
hare = FLOW_CHECKED_MOD((((hare * hare) + 1)), (q));
lam = (lam + 1);
}
if (hare == 0) {
return 1;
}
return 0;
}
void sieve_upto_i64(int64_t n) {
is_comp = ((int8_t*)(calloc((n + 1), 1)));
is_comp[0] = 1;
is_comp[1] = 1;
int64_t lim = ((int64_t)(sqrt(((double)(n)))));
int64_t i = 2;
while (i <= lim) {
if (is_comp[i] == 0) {
int64_t j = (i * i);
while (j <= n) {
is_comp[j] = 1;
j = (j + i);
}
}
i = (i + 1);
}
int64_t cnt = 0;
i = 2;
while (i <= n) {
if (is_comp[i] == 0) {
cnt = (cnt + 1);
}
i = (i + 1);
}
primes_arr = ((int32_t*)(malloc((cnt * 4))));
num_primes = 0;
i = 2;
while (i <= n) {
if (is_comp[i] == 0) {
primes_arr[num_primes] = ((int32_t)(i));
num_primes = (num_primes + 1);
}
i = (i + 1);
}
}
int32_t prime_factors_unique_i32_ptr_i32(int32_t n, int32_t* out) {
int32_t x = n;
int32_t cnt = 0;
int32_t i = 0;
while (i < num_primes) {
int32_t p = primes_arr[i];
if ((((int64_t)(p)) * ((int64_t)(p))) > ((int64_t)(x))) {
break;
}
if (FLOW_CHECKED_MOD((x), (p)) == 0) {
out[cnt] = p;
cnt = (cnt + 1);
while (FLOW_CHECKED_MOD((x), (p)) == 0) {
x = FLOW_CHECKED_DIV((x), (p));
}
}
i = (i + 1);
}
if (x > 1) {
out[cnt] = x;
cnt = (cnt + 1);
}
return cnt;
}
int32_t main(void) {
sieve_upto_i64(LIMIT);
int32_t* good_primes = (int32_t*)(((int32_t*)(malloc((((int64_t)(num_primes)) * 4)))));
int32_t num_good = 0;
int32_t* factors_buf = (int32_t*)(((int32_t*)(malloc((32 * 4)))));
int32_t pi = 0;
while (pi < num_primes) {
int32_t q = primes_arr[pi];
if (q == 2) {
good_primes[num_good] = q;
num_good = (num_good + 1);
} else {
if ((q & 3) == 1) {
if (hits_zero_mod_prime_k2_i64(((int64_t)(q))) != 0) {
int32_t nf = prime_factors_unique_i32_ptr_i32((q - 1), factors_buf);
int32_t ok = 1;
int32_t fi = 0;
while (fi < nf) {
int32_t p = factors_buf[fi];
if (p != 2) {
if (hits_zero_mod_prime_i64_i64(((int64_t)(q)), ((int64_t)(p))) == 0) {
ok = 0;
}
}
if (ok == 0) {
break;
}
fi = (fi + 1);
}
if (ok != 0) {
good_primes[num_good] = q;
num_good = (num_good + 1);
}
}
}
}
pi = (pi + 1);
}
int64_t cap = FLOW_CHECKED_SHL((1), (20));
int32_t* prods = (int32_t*)(((int32_t*)(malloc((cap * 4)))));
int64_t len = 1;
prods[0] = 1;
int32_t pidx = 0;
while (pidx < num_good) {
int32_t p = good_primes[pidx];
int64_t base_len = len;
int64_t i = 0;
while (i < base_len) {
int64_t v = (((int64_t)(prods[i])) * ((int64_t)(p)));
if (v <= LIMIT) {
if (len >= cap) {
int64_t new_cap = FLOW_CHECKED_SHL((cap), (1));
int32_t* newp = (int32_t*)(((int32_t*)(malloc((new_cap * 4)))));
memcpy(((void*)(newp)), ((void*)(prods)), (cap * 4));
free(prods);
prods = newp;
cap = new_cap;
}
prods[len] = ((int32_t)(v));
len = (len + 1);
}
i = (i + 1);
}
pidx = (pidx + 1);
}
int64_t total = 0;
int64_t i = 0;
while (i < len) {
total = (total + ((int64_t)(prods[i])));
i = (i + 1);
}
printf("%lld\n", total);
free(is_comp);
free(primes_arr);
free(good_primes);
free(factors_buf);
free(prods);
return 0;
}