# Project Euler 795
# Alternating GCD Sum — G(12345678).
# Ported from native C to pure Flow. Uses i128 for prime power calculations.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
function pow_i(p: i64, e: i64) -> i64 {
let mut r: i64 = 1
for i in 0..e {
r = r * p
}
return r
}
function a_prime_power(p: i64, e: i64) -> i64 {
if e == 0 {
return 1
}
if (e & 1) == 1 {
let k: i64 = e >> 1
return pow_i(p, e - 1) * (2 * pow_i(p, k + 1) - 1)
}
let k: i64 = e >> 1
return pow_i(p, e - 1) * ((p + 1) * pow_i(p, k) - 1)
}
function main() -> i32 {
let N: i64 = 12345678
let limit: i64 = N / 2
let spf: ptr<i64> = calloc(limit + 1, 8) as ptr<i64>
let primes: ptr<i64> = malloc((limit + 1) * 8) as ptr<i64>
let mut pc: i64 = 0
for i in 2..(limit + 1) {
if spf[i] == 0 {
spf[i] = i
primes[pc] = i
pc = pc + 1
}
for j in 0..pc {
let p: i64 = primes[j]
let x: i64 = p * i
if x > limit || p > spf[i] {
break
}
spf[x] = p
if p == spf[i] {
break
}
}
}
let c2: ptr<i64> = calloc(65, 8) as ptr<i64>
for a in 1..65 {
if ((1 as i64) << a) > N {
break
}
c2[a] = a_prime_power(2, a) - ((1 as i64) << a)
}
let odd_cnt: i64 = (N + 1) / 2
let mut total: i64 = -(odd_cnt * odd_cnt)
let mut m: i64 = 1
while m <= limit {
let mut a_m: i64 = 1
if m != 1 {
let mut n: i64 = m
a_m = 1
while n > 1 {
let p: i64 = spf[n]
let mut e: i64 = 0
while n % p == 0 {
n = n / p
e = e + 1
}
a_m = a_m * a_prime_power(p, e)
}
}
let mut a: i64 = 1
let mut n: i64 = m << 1
while n <= N {
total = total + a_m * c2[a]
a = a + 1
n = n << 1
}
m = m + 2
}
printf("%lld\n", total)
free(spf as ptr<void>)
free(primes as ptr<void>)
free(c2 as ptr<void>)
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 pow_i_i64_i64(int64_t p, int64_t e);
int64_t a_prime_power_i64_i64(int64_t p, int64_t e);
int32_t main(void);
int64_t pow_i_i64_i64(int64_t p, int64_t e) {
int64_t r = 1;
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= e) ? i < e : i > e; i += (0 <= e) ? 1 : -1) {
r = (r * p);
}
return r;
}
int64_t a_prime_power_i64_i64(int64_t p, int64_t e) {
if (e == 0) {
return 1;
}
if ((e & 1) == 1) {
int64_t k = FLOW_CHECKED_SHR((e), (1));
return (pow_i_i64_i64(p, (e - 1)) * ((2 * pow_i_i64_i64(p, (k + 1))) - 1));
}
int64_t k = FLOW_CHECKED_SHR((e), (1));
return (pow_i_i64_i64(p, (e - 1)) * (((p + 1) * pow_i_i64_i64(p, k)) - 1));
}
int32_t main(void) {
int64_t N = 12345678;
int64_t limit = FLOW_CHECKED_DIV((N), (2));
int64_t* spf = (int64_t*)(((int64_t*)(calloc((limit + 1), 8))));
int64_t* primes = (int64_t*)(((int64_t*)(malloc(((limit + 1) * 8)))));
int64_t pc = 0;
int32_t __flow_step_2 = 1;
for (int32_t i = 2; (2 <= (limit + 1)) ? i < (limit + 1) : i > (limit + 1); i += (2 <= (limit + 1)) ? 1 : -1) {
if (spf[i] == 0) {
spf[i] = i;
primes[pc] = i;
pc = (pc + 1);
}
int32_t __flow_step_3 = 1;
for (int32_t j = 0; (0 <= pc) ? j < pc : j > pc; j += (0 <= pc) ? 1 : -1) {
int64_t p = primes[j];
int64_t x = (p * i);
if ((x > limit || p > spf[i])) {
break;
}
spf[x] = p;
if (p == spf[i]) {
break;
}
}
}
int64_t* c2 = (int64_t*)(((int64_t*)(calloc(65, 8))));
int32_t __flow_step_4 = 1;
for (int32_t a = 1; (1 <= 65) ? a < 65 : a > 65; a += (1 <= 65) ? 1 : -1) {
if (FLOW_CHECKED_SHL((((int64_t)(1))), (a)) > N) {
break;
}
c2[a] = (a_prime_power_i64_i64(2, a) - FLOW_CHECKED_SHL((((int64_t)(1))), (a)));
}
int64_t odd_cnt = FLOW_CHECKED_DIV(((N + 1)), (2));
int64_t total = (-(odd_cnt * odd_cnt));
int64_t m = 1;
while (m <= limit) {
int64_t a_m = 1;
if (m != 1) {
int64_t n = m;
a_m = 1;
while (n > 1) {
int64_t p = spf[n];
int64_t e = 0;
while (FLOW_CHECKED_MOD((n), (p)) == 0) {
n = FLOW_CHECKED_DIV((n), (p));
e = (e + 1);
}
a_m = (a_m * a_prime_power_i64_i64(p, e));
}
}
int64_t a = 1;
int64_t n = FLOW_CHECKED_SHL((m), (1));
while (n <= N) {
total = (total + (a_m * c2[a]));
a = (a + 1);
n = FLOW_CHECKED_SHL((n), (1));
}
m = (m + 2);
}
printf("%lld\n", total);
free(((void*)(spf)));
free(((void*)(primes)));
free(((void*)(c2)));
return 0;
}