Problem 387
Sum of right-truncatable Harshad primes whose Harshad parents are strong, < 10^14.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^3) | O(n log log n) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Sieve or enumeration |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 387
# Sum of right-truncatable Harshad primes whose Harshad parents are strong, < 10^14.
function mulmod(a: i64, b: i64, mod: i64) -> i64 {
let mut x: i64 = a % mod
if x < 0 { x = x + mod }
let mut y: i64 = b % mod
if y < 0 { y = y + mod }
let mut res: i64 = 0
while y > 0 {
if y % 2 == 1 {
res = res + x
if res >= mod { res = res - mod }
}
x = x + x
if x >= mod { x = x - mod }
y = y / 2
}
return res
}
function powmod(base0: i64, exp0: i64, mod: i64) -> i64 {
let mut result: i64 = 1
let mut base: i64 = base0 % mod
let mut exp: i64 = exp0
while exp > 0 {
if exp % 2 == 1 { result = mulmod(result, base, mod) }
base = mulmod(base, base, mod)
exp = exp / 2
}
return result
}
function is_prime(p: i64) -> i32 {
if p < 2 { return 0 }
if p < 31 {
# bitmask of primes < 31
let mask: i64 = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) | (1 << 23) | (1 << 29)
if (mask & (1 << (p as i32))) != 0 { return 1 }
return 0
}
if p % 2 == 0 || p % 3 == 0 || p % 5 == 0 || p % 7 == 0 || p % 11 == 0 || p % 13 == 0 || p % 17 == 0 {
return 0
}
if p < 17 * 19 { return 1 }
let sps: ptr<i64> = calloc(18, 8)
if sps == null { return 0 }
sps[0]=19; sps[1]=23; sps[2]=29; sps[3]=31; sps[4]=37; sps[5]=41
sps[6]=43; sps[7]=47; sps[8]=53; sps[9]=59; sps[10]=61; sps[11]=67
sps[12]=71; sps[13]=73; sps[14]=79; sps[15]=83; sps[16]=89; sps[17]=97
let mut si: i32 = 0
while si < 18 {
if p % sps[si] == 0 {
free(sps)
return 0
}
si = si + 1
}
free(sps)
# Miller-Rabin bases
let bases: ptr<i64> = calloc(7, 8)
let mut nb: i32 = 0
if p < 5329 {
bases[0] = 377687; nb = 1
} elif p < 9080191 {
bases[0] = 31; bases[1] = 73; nb = 2
} elif p < 4759123141 {
bases[0] = 2; bases[1] = 7; bases[2] = 61; nb = 3
} elif p < 1122004669633 {
bases[0] = 2; bases[1] = 13; bases[2] = 23; bases[3] = 1662803; nb = 4
} else {
bases[0] = 2; bases[1] = 325; bases[2] = 9375; bases[3] = 28178
bases[4] = 450775; bases[5] = 9780504; bases[6] = 1795265022; nb = 7
}
let mut d: i64 = (p - 1) / 2
let mut shift: i32 = 0
while d % 2 == 0 {
shift = shift + 1
d = d / 2
}
let mut bi: i32 = 0
while bi < nb {
let base: i64 = bases[bi] % p
if base == 0 {
bi = bi + 1
continue
}
let mut x: i64 = powmod(base, d, p)
if x != 1 && x != p - 1 {
let mut maybe: i32 = 0
let mut r: i32 = 0
while r < shift {
x = mulmod(x, x, p)
if x == 1 {
free(bases)
return 0
}
if x == p - 1 {
maybe = 1
break
}
r = r + 1
}
if maybe == 0 {
free(bases)
return 0
}
}
bi = bi + 1
}
free(bases)
return 1
}
function digit_sum(x0: i64) -> i64 {
let mut x: i64 = x0
let mut result: i64 = 0
while x >= 10 {
result = result + x % 10
x = x / 10
}
return result + x
}
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function main() -> i32 {
let max_digits: i32 = 14
# Harshad numbers by digit length; strong Harshad flagged separately
let CAP: i64 = 200000
let todo: ptr<i64> = calloc(CAP, 8)
let nextv: ptr<i64> = calloc(CAP, 8)
let strong: ptr<i8> = calloc(CAP, 1)
let strong_next: ptr<i8> = calloc(CAP, 1)
if todo == null || nextv == null || strong == null || strong_next == null { return 1 }
let mut tlen: i64 = 0
let mut d0: i64 = 1
while d0 <= 9 {
todo[tlen] = d0
strong[tlen] = 0
tlen = tlen + 1
d0 = d0 + 1
}
let mut result: i64 = 0
let mut num_digits: i32 = 1
while num_digits < max_digits {
num_digits = num_digits + 1
let mut nlen: i64 = 0
let mut ix: i64 = 0
while ix < tlen {
let x: i64 = todo[ix]
let is_strong_parent: i32 = strong[ix] as i32
let mut digit: i64 = 0
while digit <= 9 {
let current: i64 = x * 10 + digit
if is_strong_parent == 1 {
if is_prime(current) == 1 {
result = result + current
}
}
let reduced: i64 = digit_sum(current)
if current % reduced == 0 {
nextv[nlen] = current
if is_prime(current / reduced) == 1 {
strong_next[nlen] = 1
} else {
strong_next[nlen] = 0
}
nlen = nlen + 1
if nlen >= CAP {
printf("overflow\n")
return 1
}
}
digit = digit + 1
}
ix = ix + 1
}
# swap buffers
let mut j: i64 = 0
while j < nlen {
todo[j] = nextv[j]
strong[j] = strong_next[j]
j = j + 1
}
tlen = nlen
}
printf("%lld\n", result)
free(strong_next)
free(strong)
free(nextv)
free(todo)
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 mulmod_i64_i64_i64(int64_t a, int64_t b, int64_t mod);
int64_t powmod_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod);
int32_t is_prime_i64(int64_t p);
int64_t digit_sum_i64(int64_t x0);
int32_t main(void);
int64_t mulmod_i64_i64_i64(int64_t a, int64_t b, int64_t mod) {
int64_t x = FLOW_CHECKED_MOD((a), (mod));
if (x < 0) {
x = (x + mod);
}
int64_t y = FLOW_CHECKED_MOD((b), (mod));
if (y < 0) {
y = (y + mod);
}
int64_t res = 0;
while (y > 0) {
if (FLOW_CHECKED_MOD((y), (2)) == 1) {
res = (res + x);
if (res >= mod) {
res = (res - mod);
}
}
x = (x + x);
if (x >= mod) {
x = (x - mod);
}
y = FLOW_CHECKED_DIV((y), (2));
}
return res;
}
int64_t powmod_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod) {
int64_t result = 1;
int64_t base = FLOW_CHECKED_MOD((base0), (mod));
int64_t exp = exp0;
while (exp > 0) {
if (FLOW_CHECKED_MOD((exp), (2)) == 1) {
result = mulmod_i64_i64_i64(result, base, mod);
}
base = mulmod_i64_i64_i64(base, base, mod);
exp = FLOW_CHECKED_DIV((exp), (2));
}
return result;
}
int32_t is_prime_i64(int64_t p) {
if (p < 2) {
return 0;
}
if (p < 31) {
int64_t mask = (((((((((FLOW_CHECKED_SHL((1), (2)) | FLOW_CHECKED_SHL((1), (3))) | FLOW_CHECKED_SHL((1), (5))) | FLOW_CHECKED_SHL((1), (7))) | FLOW_CHECKED_SHL((1), (11))) | FLOW_CHECKED_SHL((1), (13))) | FLOW_CHECKED_SHL((1), (17))) | FLOW_CHECKED_SHL((1), (19))) | FLOW_CHECKED_SHL((1), (23))) | FLOW_CHECKED_SHL((1), (29)));
if ((mask & FLOW_CHECKED_SHL((1), (((int32_t)(p))))) != 0) {
return 1;
}
return 0;
}
if (((((((FLOW_CHECKED_MOD((p), (2)) == 0 || FLOW_CHECKED_MOD((p), (3)) == 0) || FLOW_CHECKED_MOD((p), (5)) == 0) || FLOW_CHECKED_MOD((p), (7)) == 0) || FLOW_CHECKED_MOD((p), (11)) == 0) || FLOW_CHECKED_MOD((p), (13)) == 0) || FLOW_CHECKED_MOD((p), (17)) == 0)) {
return 0;
}
if (p < (17 * 19)) {
return 1;
}
int64_t* sps = (int64_t*)(calloc(18, 8));
if (sps == NULL) {
return 0;
}
sps[0] = 19;
sps[1] = 23;
sps[2] = 29;
sps[3] = 31;
sps[4] = 37;
sps[5] = 41;
sps[6] = 43;
sps[7] = 47;
sps[8] = 53;
sps[9] = 59;
sps[10] = 61;
sps[11] = 67;
sps[12] = 71;
sps[13] = 73;
sps[14] = 79;
sps[15] = 83;
sps[16] = 89;
sps[17] = 97;
int32_t si = 0;
while (si < 18) {
if (FLOW_CHECKED_MOD((p), (sps[si])) == 0) {
free(sps);
return 0;
}
si = (si + 1);
}
free(sps);
int64_t* bases = (int64_t*)(calloc(7, 8));
int32_t nb = 0;
if (p < 5329) {
bases[0] = 377687;
nb = 1;
} else if (p < 9080191) {
bases[0] = 31;
bases[1] = 73;
nb = 2;
} else if (p < 4759123141) {
bases[0] = 2;
bases[1] = 7;
bases[2] = 61;
nb = 3;
} else if (p < 1122004669633) {
bases[0] = 2;
bases[1] = 13;
bases[2] = 23;
bases[3] = 1662803;
nb = 4;
} else {
bases[0] = 2;
bases[1] = 325;
bases[2] = 9375;
bases[3] = 28178;
bases[4] = 450775;
bases[5] = 9780504;
bases[6] = 1795265022;
nb = 7;
}
int64_t d = FLOW_CHECKED_DIV(((p - 1)), (2));
int32_t shift = 0;
while (FLOW_CHECKED_MOD((d), (2)) == 0) {
shift = (shift + 1);
d = FLOW_CHECKED_DIV((d), (2));
}
int32_t bi = 0;
while (bi < nb) {
int64_t base = FLOW_CHECKED_MOD((bases[bi]), (p));
if (base == 0) {
bi = (bi + 1);
continue;
}
int64_t x = powmod_i64_i64_i64(base, d, p);
if ((x != 1 && x != (p - 1))) {
int32_t maybe = 0;
int32_t r = 0;
while (r < shift) {
x = mulmod_i64_i64_i64(x, x, p);
if (x == 1) {
free(bases);
return 0;
}
if (x == (p - 1)) {
maybe = 1;
break;
}
r = (r + 1);
}
if (maybe == 0) {
free(bases);
return 0;
}
}
bi = (bi + 1);
}
free(bases);
return 1;
}
int64_t digit_sum_i64(int64_t x0) {
int64_t x = x0;
int64_t result = 0;
while (x >= 10) {
result = (result + FLOW_CHECKED_MOD((x), (10)));
x = FLOW_CHECKED_DIV((x), (10));
}
return (result + x);
}
int32_t main(void) {
int32_t max_digits = 14;
int64_t CAP = 200000;
int64_t* todo = (int64_t*)(calloc(CAP, 8));
int64_t* nextv = (int64_t*)(calloc(CAP, 8));
int8_t* strong = (int8_t*)(calloc(CAP, 1));
int8_t* strong_next = (int8_t*)(calloc(CAP, 1));
if ((((todo == NULL || nextv == NULL) || strong == NULL) || strong_next == NULL)) {
return 1;
}
int64_t tlen = 0;
int64_t d0 = 1;
while (d0 <= 9) {
todo[tlen] = d0;
strong[tlen] = 0;
tlen = (tlen + 1);
d0 = (d0 + 1);
}
int64_t result = 0;
int32_t num_digits = 1;
while (num_digits < max_digits) {
num_digits = (num_digits + 1);
int64_t nlen = 0;
int64_t ix = 0;
while (ix < tlen) {
int64_t x = todo[ix];
int32_t is_strong_parent = ((int32_t)(strong[ix]));
int64_t digit = 0;
while (digit <= 9) {
int64_t current = ((x * 10) + digit);
if (is_strong_parent == 1) {
if (is_prime_i64(current) == 1) {
result = (result + current);
}
}
int64_t reduced = digit_sum_i64(current);
if (FLOW_CHECKED_MOD((current), (reduced)) == 0) {
nextv[nlen] = current;
if (is_prime_i64(FLOW_CHECKED_DIV((current), (reduced))) == 1) {
strong_next[nlen] = 1;
} else {
strong_next[nlen] = 0;
}
nlen = (nlen + 1);
if (nlen >= CAP) {
printf("overflow\n");
return 1;
}
}
digit = (digit + 1);
}
ix = (ix + 1);
}
int64_t j = 0;
while (j < nlen) {
todo[j] = nextv[j];
strong[j] = strong_next[j];
j = (j + 1);
}
tlen = nlen;
}
printf("%lld\n", result);
free(strong_next);
free(strong);
free(nextv);
free(todo);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("overflow\n\00") {addr_space = 0 : i32} : !llvm.array<10 x i8>
llvm.mlir.global internal constant @str_1("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%0 = arith.remsi %arg0, %arg2 : i64
%1 = llvm.mlir.constant(1 : i64) : i64
%2 = llvm.alloca %1 x i64 : (i64) -> !llvm.ptr
llvm.store %0, %2 : i64, !llvm.ptr
%3 = llvm.load %2 : !llvm.ptr -> i64
%4 = arith.constant 0 : i32
%6 = arith.extsi %4 : i32 to i64
%5 = arith.cmpi slt, %3, %6 : i64
cf.cond_br %5, ^bb0, ^bb1
^bb0:
%7 = llvm.load %2 : !llvm.ptr -> i64
%8 = arith.addi %7, %arg2 : i64
llvm.store %8, %2 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%9 = arith.remsi %arg1, %arg2 : i64
%10 = llvm.mlir.constant(1 : i64) : i64
%11 = llvm.alloca %10 x i64 : (i64) -> !llvm.ptr
llvm.store %9, %11 : i64, !llvm.ptr
%12 = llvm.load %11 : !llvm.ptr -> i64
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi slt, %12, %15 : i64
cf.cond_br %14, ^bb3, ^bb4
^bb3:
%16 = llvm.load %11 : !llvm.ptr -> i64
%17 = arith.addi %16, %arg2 : i64
llvm.store %17, %11 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%18 = arith.constant 0 : i32
%19 = arith.extsi %18 : i32 to i64
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x i64 : (i64) -> !llvm.ptr
llvm.store %19, %21 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%22 = llvm.load %11 : !llvm.ptr -> i64
%23 = arith.constant 0 : i32
%25 = arith.extsi %23 : i32 to i64
%24 = arith.cmpi sgt, %22, %25 : i64
cf.cond_br %24, ^bb7, ^bb8
^bb7:
%26 = llvm.load %11 : !llvm.ptr -> i64
%27 = arith.constant 2 : i32
%29 = arith.extsi %27 : i32 to i64
%28 = arith.remsi %26, %29 : i64
%30 = arith.constant 1 : i32
%32 = arith.extsi %30 : i32 to i64
%31 = arith.cmpi eq, %28, %32 : i64
cf.cond_br %31, ^bb9, ^bb10
^bb9:
%33 = llvm.load %21 : !llvm.ptr -> i64
%34 = llvm.load %2 : !llvm.ptr -> i64
%35 = arith.addi %33, %34 : i64
llvm.store %35, %21 : i64, !llvm.ptr
%36 = llvm.load %21 : !llvm.ptr -> i64
%37 = arith.cmpi sge, %36, %arg2 : i64
cf.cond_br %37, ^bb12, ^bb13
^bb12:
%38 = llvm.load %21 : !llvm.ptr -> i64
%39 = arith.subi %38, %arg2 : i64
llvm.store %39, %21 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%40 = llvm.load %2 : !llvm.ptr -> i64
%41 = llvm.load %2 : !llvm.ptr -> i64
%42 = arith.addi %40, %41 : i64
llvm.store %42, %2 : i64, !llvm.ptr
%43 = llvm.load %2 : !llvm.ptr -> i64
%44 = arith.cmpi sge, %43, %arg2 : i64
cf.cond_br %44, ^bb15, ^bb16
^bb15:
%45 = llvm.load %2 : !llvm.ptr -> i64
%46 = arith.subi %45, %arg2 : i64
llvm.store %46, %2 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%47 = llvm.load %11 : !llvm.ptr -> i64
%48 = arith.constant 2 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.divsi %47, %50 : i64
llvm.store %49, %11 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%51 = llvm.load %21 : !llvm.ptr -> i64
func.return %51 : i64
}
func.func @powmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%52 = arith.constant 1 : i32
%53 = arith.extsi %52 : i32 to i64
%54 = llvm.mlir.constant(1 : i64) : i64
%55 = llvm.alloca %54 x i64 : (i64) -> !llvm.ptr
llvm.store %53, %55 : i64, !llvm.ptr
%56 = arith.remsi %arg0, %arg2 : i64
%57 = llvm.mlir.constant(1 : i64) : i64
%58 = llvm.alloca %57 x i64 : (i64) -> !llvm.ptr
llvm.store %56, %58 : i64, !llvm.ptr
%59 = llvm.mlir.constant(1 : i64) : i64
%60 = llvm.alloca %59 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %60 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%61 = llvm.load %60 : !llvm.ptr -> i64
%62 = arith.constant 0 : i32
%64 = arith.extsi %62 : i32 to i64
%63 = arith.cmpi sgt, %61, %64 : i64
cf.cond_br %63, ^bb19, ^bb20
^bb19:
%65 = llvm.load %60 : !llvm.ptr -> i64
%66 = arith.constant 2 : i32
%68 = arith.extsi %66 : i32 to i64
%67 = arith.remsi %65, %68 : i64
%69 = arith.constant 1 : i32
%71 = arith.extsi %69 : i32 to i64
%70 = arith.cmpi eq, %67, %71 : i64
cf.cond_br %70, ^bb21, ^bb22
^bb21:
%73 = llvm.load %55 : !llvm.ptr -> i64
%74 = llvm.load %58 : !llvm.ptr -> i64
%72 = func.call @mulmod(%73, %74, %arg2) : (i64, i64, i64) -> i64
llvm.store %72, %55 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%76 = llvm.load %58 : !llvm.ptr -> i64
%77 = llvm.load %58 : !llvm.ptr -> i64
%75 = func.call @mulmod(%76, %77, %arg2) : (i64, i64, i64) -> i64
llvm.store %75, %58 : i64, !llvm.ptr
%78 = llvm.load %60 : !llvm.ptr -> i64
%79 = arith.constant 2 : i32
%81 = arith.extsi %79 : i32 to i64
%80 = arith.divsi %78, %81 : i64
llvm.store %80, %60 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%82 = llvm.load %55 : !llvm.ptr -> i64
func.return %82 : i64
}
func.func @is_prime(%arg0: i64) -> i32 {
%83 = arith.constant 2 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.cmpi slt, %arg0, %85 : i64
cf.cond_br %84, ^bb24, ^bb25
^bb24:
%86 = arith.constant 0 : i32
func.return %86 : i32
^bb25:
cf.br ^bb26
^bb26:
%87 = arith.constant 31 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.cmpi slt, %arg0, %89 : i64
cf.cond_br %88, ^bb27, ^bb28
^bb27:
%90 = arith.constant 1 : i32
%91 = arith.constant 2 : i32
%92 = arith.shli %90, %91 : i32
%93 = arith.constant 1 : i32
%94 = arith.constant 3 : i32
%95 = arith.shli %93, %94 : i32
%96 = arith.ori %92, %95 : i32
%97 = arith.constant 1 : i32
%98 = arith.constant 5 : i32
%99 = arith.shli %97, %98 : i32
%100 = arith.ori %96, %99 : i32
%101 = arith.constant 1 : i32
%102 = arith.constant 7 : i32
%103 = arith.shli %101, %102 : i32
%104 = arith.ori %100, %103 : i32
%105 = arith.constant 1 : i32
%106 = arith.constant 11 : i32
%107 = arith.shli %105, %106 : i32
%108 = arith.ori %104, %107 : i32
%109 = arith.constant 1 : i32
%110 = arith.constant 13 : i32
%111 = arith.shli %109, %110 : i32
%112 = arith.ori %108, %111 : i32
%113 = arith.constant 1 : i32
%114 = arith.constant 17 : i32
%115 = arith.shli %113, %114 : i32
%116 = arith.ori %112, %115 : i32
%117 = arith.constant 1 : i32
%118 = arith.constant 19 : i32
%119 = arith.shli %117, %118 : i32
%120 = arith.ori %116, %119 : i32
%121 = arith.constant 1 : i32
%122 = arith.constant 23 : i32
%123 = arith.shli %121, %122 : i32
%124 = arith.ori %120, %123 : i32
%125 = arith.constant 1 : i32
%126 = arith.constant 29 : i32
%127 = arith.shli %125, %126 : i32
%128 = arith.ori %124, %127 : i32
%129 = arith.extsi %128 : i32 to i64
%130 = arith.constant 1 : i32
%131 = arith.trunci %arg0 : i64 to i32
%132 = arith.shli %130, %131 : i32
%134 = arith.extsi %132 : i32 to i64
%133 = arith.andi %129, %134 : i64
%135 = arith.constant 0 : i32
%137 = arith.extsi %135 : i32 to i64
%136 = arith.cmpi ne, %133, %137 : i64
cf.cond_br %136, ^bb30, ^bb31
^bb30:
%138 = arith.constant 1 : i32
func.return %138 : i32
^bb31:
cf.br ^bb32
^bb32:
%139 = arith.constant 0 : i32
func.return %139 : i32
^bb28:
cf.br ^bb29
^bb29:
%140 = arith.constant 2 : i32
%142 = arith.extsi %140 : i32 to i64
%141 = arith.remsi %arg0, %142 : i64
%143 = arith.constant 0 : i32
%145 = arith.extsi %143 : i32 to i64
%144 = arith.cmpi eq, %141, %145 : i64
%146 = scf.if %144 -> (i1) {
%147 = arith.constant true
scf.yield %147 : i1
} else {
%148 = arith.constant 3 : i32
%150 = arith.extsi %148 : i32 to i64
%149 = arith.remsi %arg0, %150 : i64
%151 = arith.constant 0 : i32
%153 = arith.extsi %151 : i32 to i64
%152 = arith.cmpi eq, %149, %153 : i64
scf.yield %152 : i1
}
%154 = scf.if %146 -> (i1) {
%155 = arith.constant true
scf.yield %155 : i1
} else {
%156 = arith.constant 5 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.remsi %arg0, %158 : i64
%159 = arith.constant 0 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.cmpi eq, %157, %161 : i64
scf.yield %160 : i1
}
%162 = scf.if %154 -> (i1) {
%163 = arith.constant true
scf.yield %163 : i1
} else {
%164 = arith.constant 7 : i32
%166 = arith.extsi %164 : i32 to i64
%165 = arith.remsi %arg0, %166 : i64
%167 = arith.constant 0 : i32
%169 = arith.extsi %167 : i32 to i64
%168 = arith.cmpi eq, %165, %169 : i64
scf.yield %168 : i1
}
%170 = scf.if %162 -> (i1) {
%171 = arith.constant true
scf.yield %171 : i1
} else {
%172 = arith.constant 11 : i32
%174 = arith.extsi %172 : i32 to i64
%173 = arith.remsi %arg0, %174 : i64
%175 = arith.constant 0 : i32
%177 = arith.extsi %175 : i32 to i64
%176 = arith.cmpi eq, %173, %177 : i64
scf.yield %176 : i1
}
%178 = scf.if %170 -> (i1) {
%179 = arith.constant true
scf.yield %179 : i1
} else {
%180 = arith.constant 13 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.remsi %arg0, %182 : i64
%183 = arith.constant 0 : i32
%185 = arith.extsi %183 : i32 to i64
%184 = arith.cmpi eq, %181, %185 : i64
scf.yield %184 : i1
}
%186 = scf.if %178 -> (i1) {
%187 = arith.constant true
scf.yield %187 : i1
} else {
%188 = arith.constant 17 : i32
%190 = arith.extsi %188 : i32 to i64
%189 = arith.remsi %arg0, %190 : i64
%191 = arith.constant 0 : i32
%193 = arith.extsi %191 : i32 to i64
%192 = arith.cmpi eq, %189, %193 : i64
scf.yield %192 : i1
}
cf.cond_br %186, ^bb33, ^bb34
^bb33:
%194 = arith.constant 0 : i32
func.return %194 : i32
^bb34:
cf.br ^bb35
^bb35:
%195 = arith.constant 17 : i32
%196 = arith.constant 19 : i32
%197 = arith.muli %195, %196 : i32
%199 = arith.extsi %197 : i32 to i64
%198 = arith.cmpi slt, %arg0, %199 : i64
cf.cond_br %198, ^bb36, ^bb37
^bb36:
%200 = arith.constant 1 : i32
func.return %200 : i32
^bb37:
cf.br ^bb38
^bb38:
%202 = arith.constant 18 : i32
%203 = arith.constant 8 : i32
%204 = arith.extsi %202 : i32 to i64
%205 = arith.extsi %203 : i32 to i64
%201 = func.call @calloc(%204, %205) : (i64, i64) -> !llvm.ptr
%206 = llvm.mlir.zero : !llvm.ptr
%207 = llvm.icmp "eq" %201, %206 : !llvm.ptr
cf.cond_br %207, ^bb39, ^bb40
^bb39:
%208 = arith.constant 0 : i32
func.return %208 : i32
^bb40:
cf.br ^bb41
^bb41:
%209 = arith.constant 19 : i32
%210 = arith.constant 0 : i32
%211 = arith.extsi %209 : i32 to i64
%212 = arith.extsi %210 : i32 to i64
%213 = llvm.getelementptr %201[%212] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %211, %213 : i64, !llvm.ptr
%214 = arith.constant 23 : i32
%215 = arith.constant 1 : i32
%216 = arith.extsi %214 : i32 to i64
%217 = arith.extsi %215 : i32 to i64
%218 = llvm.getelementptr %201[%217] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %216, %218 : i64, !llvm.ptr
%219 = arith.constant 29 : i32
%220 = arith.constant 2 : i32
%221 = arith.extsi %219 : i32 to i64
%222 = arith.extsi %220 : i32 to i64
%223 = llvm.getelementptr %201[%222] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %221, %223 : i64, !llvm.ptr
%224 = arith.constant 31 : i32
%225 = arith.constant 3 : i32
%226 = arith.extsi %224 : i32 to i64
%227 = arith.extsi %225 : i32 to i64
%228 = llvm.getelementptr %201[%227] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %226, %228 : i64, !llvm.ptr
%229 = arith.constant 37 : i32
%230 = arith.constant 4 : i32
%231 = arith.extsi %229 : i32 to i64
%232 = arith.extsi %230 : i32 to i64
%233 = llvm.getelementptr %201[%232] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %231, %233 : i64, !llvm.ptr
%234 = arith.constant 41 : i32
%235 = arith.constant 5 : i32
%236 = arith.extsi %234 : i32 to i64
%237 = arith.extsi %235 : i32 to i64
%238 = llvm.getelementptr %201[%237] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %236, %238 : i64, !llvm.ptr
%239 = arith.constant 43 : i32
%240 = arith.constant 6 : i32
%241 = arith.extsi %239 : i32 to i64
%242 = arith.extsi %240 : i32 to i64
%243 = llvm.getelementptr %201[%242] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %241, %243 : i64, !llvm.ptr
%244 = arith.constant 47 : i32
%245 = arith.constant 7 : i32
%246 = arith.extsi %244 : i32 to i64
%247 = arith.extsi %245 : i32 to i64
%248 = llvm.getelementptr %201[%247] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %246, %248 : i64, !llvm.ptr
%249 = arith.constant 53 : i32
%250 = arith.constant 8 : i32
%251 = arith.extsi %249 : i32 to i64
%252 = arith.extsi %250 : i32 to i64
%253 = llvm.getelementptr %201[%252] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %251, %253 : i64, !llvm.ptr
%254 = arith.constant 59 : i32
%255 = arith.constant 9 : i32
%256 = arith.extsi %254 : i32 to i64
%257 = arith.extsi %255 : i32 to i64
%258 = llvm.getelementptr %201[%257] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %256, %258 : i64, !llvm.ptr
%259 = arith.constant 61 : i32
%260 = arith.constant 10 : i32
%261 = arith.extsi %259 : i32 to i64
%262 = arith.extsi %260 : i32 to i64
%263 = llvm.getelementptr %201[%262] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %261, %263 : i64, !llvm.ptr
%264 = arith.constant 67 : i32
%265 = arith.constant 11 : i32
%266 = arith.extsi %264 : i32 to i64
%267 = arith.extsi %265 : i32 to i64
%268 = llvm.getelementptr %201[%267] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %266, %268 : i64, !llvm.ptr
%269 = arith.constant 71 : i32
%270 = arith.constant 12 : i32
%271 = arith.extsi %269 : i32 to i64
%272 = arith.extsi %270 : i32 to i64
%273 = llvm.getelementptr %201[%272] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %271, %273 : i64, !llvm.ptr
%274 = arith.constant 73 : i32
%275 = arith.constant 13 : i32
%276 = arith.extsi %274 : i32 to i64
%277 = arith.extsi %275 : i32 to i64
%278 = llvm.getelementptr %201[%277] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %276, %278 : i64, !llvm.ptr
%279 = arith.constant 79 : i32
%280 = arith.constant 14 : i32
%281 = arith.extsi %279 : i32 to i64
%282 = arith.extsi %280 : i32 to i64
%283 = llvm.getelementptr %201[%282] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %281, %283 : i64, !llvm.ptr
%284 = arith.constant 83 : i32
%285 = arith.constant 15 : i32
%286 = arith.extsi %284 : i32 to i64
%287 = arith.extsi %285 : i32 to i64
%288 = llvm.getelementptr %201[%287] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %286, %288 : i64, !llvm.ptr
%289 = arith.constant 89 : i32
%290 = arith.constant 16 : i32
%291 = arith.extsi %289 : i32 to i64
%292 = arith.extsi %290 : i32 to i64
%293 = llvm.getelementptr %201[%292] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %291, %293 : i64, !llvm.ptr
%294 = arith.constant 97 : i32
%295 = arith.constant 17 : i32
%296 = arith.extsi %294 : i32 to i64
%297 = arith.extsi %295 : i32 to i64
%298 = llvm.getelementptr %201[%297] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %296, %298 : i64, !llvm.ptr
%299 = arith.constant 0 : i32
%300 = llvm.mlir.constant(1 : i64) : i64
%301 = llvm.alloca %300 x i32 : (i64) -> !llvm.ptr
llvm.store %299, %301 : i32, !llvm.ptr
cf.br ^bb42
^bb42:
%302 = llvm.load %301 : !llvm.ptr -> i32
%303 = arith.constant 18 : i32
%304 = arith.cmpi slt, %302, %303 : i32
cf.cond_br %304, ^bb43, ^bb44
^bb43:
%306 = llvm.load %301 : !llvm.ptr -> i32
%307 = arith.extsi %306 : i32 to i64
%308 = llvm.getelementptr %201[%307] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%305 = llvm.load %308 : !llvm.ptr -> i64
%309 = arith.remsi %arg0, %305 : i64
%310 = arith.constant 0 : i32
%312 = arith.extsi %310 : i32 to i64
%311 = arith.cmpi eq, %309, %312 : i64
cf.cond_br %311, ^bb45, ^bb46
^bb45:
func.call @free(%201) : (!llvm.ptr) -> ()
%314 = arith.constant 0 : i32
func.return %314 : i32
^bb46:
cf.br ^bb47
^bb47:
%315 = llvm.load %301 : !llvm.ptr -> i32
%316 = arith.constant 1 : i32
%317 = arith.addi %315, %316 : i32
llvm.store %317, %301 : i32, !llvm.ptr
cf.br ^bb42
^bb44:
func.call @free(%201) : (!llvm.ptr) -> ()
%320 = arith.constant 7 : i32
%321 = arith.constant 8 : i32
%322 = arith.extsi %320 : i32 to i64
%323 = arith.extsi %321 : i32 to i64
%319 = func.call @calloc(%322, %323) : (i64, i64) -> !llvm.ptr
%324 = arith.constant 0 : i32
%325 = llvm.mlir.constant(1 : i64) : i64
%326 = llvm.alloca %325 x i32 : (i64) -> !llvm.ptr
llvm.store %324, %326 : i32, !llvm.ptr
%327 = arith.constant 5329 : i32
%329 = arith.extsi %327 : i32 to i64
%328 = arith.cmpi slt, %arg0, %329 : i64
cf.cond_br %328, ^bb48, ^bb49
^bb48:
%330 = arith.constant 377687 : i32
%331 = arith.constant 0 : i32
%332 = arith.extsi %330 : i32 to i64
%333 = arith.extsi %331 : i32 to i64
%334 = llvm.getelementptr %319[%333] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %332, %334 : i64, !llvm.ptr
%335 = arith.constant 1 : i32
llvm.store %335, %326 : i32, !llvm.ptr
cf.br ^bb50
^bb49:
%336 = arith.constant 9080191 : i32
%338 = arith.extsi %336 : i32 to i64
%337 = arith.cmpi slt, %arg0, %338 : i64
cf.cond_br %337, ^bb52, ^bb51
^bb52:
%339 = arith.constant 31 : i32
%340 = arith.constant 0 : i32
%341 = arith.extsi %339 : i32 to i64
%342 = arith.extsi %340 : i32 to i64
%343 = llvm.getelementptr %319[%342] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %341, %343 : i64, !llvm.ptr
%344 = arith.constant 73 : i32
%345 = arith.constant 1 : i32
%346 = arith.extsi %344 : i32 to i64
%347 = arith.extsi %345 : i32 to i64
%348 = llvm.getelementptr %319[%347] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %346, %348 : i64, !llvm.ptr
%349 = arith.constant 2 : i32
llvm.store %349, %326 : i32, !llvm.ptr
cf.br ^bb50
^bb51:
%350 = arith.constant 464155845 : i32
%352 = arith.extsi %350 : i32 to i64
%351 = arith.cmpi slt, %arg0, %352 : i64
cf.cond_br %351, ^bb54, ^bb53
^bb54:
%353 = arith.constant 2 : i32
%354 = arith.constant 0 : i32
%355 = arith.extsi %353 : i32 to i64
%356 = arith.extsi %354 : i32 to i64
%357 = llvm.getelementptr %319[%356] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %355, %357 : i64, !llvm.ptr
%358 = arith.constant 7 : i32
%359 = arith.constant 1 : i32
%360 = arith.extsi %358 : i32 to i64
%361 = arith.extsi %359 : i32 to i64
%362 = llvm.getelementptr %319[%361] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %360, %362 : i64, !llvm.ptr
%363 = arith.constant 61 : i32
%364 = arith.constant 2 : i32
%365 = arith.extsi %363 : i32 to i64
%366 = arith.extsi %364 : i32 to i64
%367 = llvm.getelementptr %319[%366] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %365, %367 : i64, !llvm.ptr
%368 = arith.constant 3 : i32
llvm.store %368, %326 : i32, !llvm.ptr
cf.br ^bb50
^bb53:
%369 = arith.constant 1117709702337 : i32
%371 = arith.extsi %369 : i32 to i64
%370 = arith.cmpi slt, %arg0, %371 : i64
cf.cond_br %370, ^bb56, ^bb55
^bb56:
%372 = arith.constant 2 : i32
%373 = arith.constant 0 : i32
%374 = arith.extsi %372 : i32 to i64
%375 = arith.extsi %373 : i32 to i64
%376 = llvm.getelementptr %319[%375] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %374, %376 : i64, !llvm.ptr
%377 = arith.constant 13 : i32
%378 = arith.constant 1 : i32
%379 = arith.extsi %377 : i32 to i64
%380 = arith.extsi %378 : i32 to i64
%381 = llvm.getelementptr %319[%380] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %379, %381 : i64, !llvm.ptr
%382 = arith.constant 23 : i32
%383 = arith.constant 2 : i32
%384 = arith.extsi %382 : i32 to i64
%385 = arith.extsi %383 : i32 to i64
%386 = llvm.getelementptr %319[%385] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %384, %386 : i64, !llvm.ptr
%387 = arith.constant 1662803 : i32
%388 = arith.constant 3 : i32
%389 = arith.extsi %387 : i32 to i64
%390 = arith.extsi %388 : i32 to i64
%391 = llvm.getelementptr %319[%390] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %389, %391 : i64, !llvm.ptr
%392 = arith.constant 4 : i32
llvm.store %392, %326 : i32, !llvm.ptr
cf.br ^bb50
^bb55:
%393 = arith.constant 2 : i32
%394 = arith.constant 0 : i32
%395 = arith.extsi %393 : i32 to i64
%396 = arith.extsi %394 : i32 to i64
%397 = llvm.getelementptr %319[%396] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %395, %397 : i64, !llvm.ptr
%398 = arith.constant 325 : i32
%399 = arith.constant 1 : i32
%400 = arith.extsi %398 : i32 to i64
%401 = arith.extsi %399 : i32 to i64
%402 = llvm.getelementptr %319[%401] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %400, %402 : i64, !llvm.ptr
%403 = arith.constant 9375 : i32
%404 = arith.constant 2 : i32
%405 = arith.extsi %403 : i32 to i64
%406 = arith.extsi %404 : i32 to i64
%407 = llvm.getelementptr %319[%406] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %405, %407 : i64, !llvm.ptr
%408 = arith.constant 28178 : i32
%409 = arith.constant 3 : i32
%410 = arith.extsi %408 : i32 to i64
%411 = arith.extsi %409 : i32 to i64
%412 = llvm.getelementptr %319[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %410, %412 : i64, !llvm.ptr
%413 = arith.constant 450775 : i32
%414 = arith.constant 4 : i32
%415 = arith.extsi %413 : i32 to i64
%416 = arith.extsi %414 : i32 to i64
%417 = llvm.getelementptr %319[%416] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %415, %417 : i64, !llvm.ptr
%418 = arith.constant 9780504 : i32
%419 = arith.constant 5 : i32
%420 = arith.extsi %418 : i32 to i64
%421 = arith.extsi %419 : i32 to i64
%422 = llvm.getelementptr %319[%421] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %420, %422 : i64, !llvm.ptr
%423 = arith.constant 1795265022 : i32
%424 = arith.constant 6 : i32
%425 = arith.extsi %423 : i32 to i64
%426 = arith.extsi %424 : i32 to i64
%427 = llvm.getelementptr %319[%426] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %425, %427 : i64, !llvm.ptr
%428 = arith.constant 7 : i32
llvm.store %428, %326 : i32, !llvm.ptr
cf.br ^bb50
^bb50:
%429 = arith.constant 1 : i32
%431 = arith.extsi %429 : i32 to i64
%430 = arith.subi %arg0, %431 : i64
%432 = arith.constant 2 : i32
%434 = arith.extsi %432 : i32 to i64
%433 = arith.divsi %430, %434 : i64
%435 = llvm.mlir.constant(1 : i64) : i64
%436 = llvm.alloca %435 x i64 : (i64) -> !llvm.ptr
llvm.store %433, %436 : i64, !llvm.ptr
%437 = arith.constant 0 : i32
%438 = llvm.mlir.constant(1 : i64) : i64
%439 = llvm.alloca %438 x i32 : (i64) -> !llvm.ptr
llvm.store %437, %439 : i32, !llvm.ptr
cf.br ^bb57
^bb57:
%440 = llvm.load %436 : !llvm.ptr -> i64
%441 = arith.constant 2 : i32
%443 = arith.extsi %441 : i32 to i64
%442 = arith.remsi %440, %443 : i64
%444 = arith.constant 0 : i32
%446 = arith.extsi %444 : i32 to i64
%445 = arith.cmpi eq, %442, %446 : i64
cf.cond_br %445, ^bb58, ^bb59
^bb58:
%447 = llvm.load %439 : !llvm.ptr -> i32
%448 = arith.constant 1 : i32
%449 = arith.addi %447, %448 : i32
llvm.store %449, %439 : i32, !llvm.ptr
%450 = llvm.load %436 : !llvm.ptr -> i64
%451 = arith.constant 2 : i32
%453 = arith.extsi %451 : i32 to i64
%452 = arith.divsi %450, %453 : i64
llvm.store %452, %436 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%454 = arith.constant 0 : i32
%455 = llvm.mlir.constant(1 : i64) : i64
%456 = llvm.alloca %455 x i32 : (i64) -> !llvm.ptr
llvm.store %454, %456 : i32, !llvm.ptr
cf.br ^bb60
^bb60:
%457 = llvm.load %456 : !llvm.ptr -> i32
%458 = llvm.load %326 : !llvm.ptr -> i32
%459 = arith.cmpi slt, %457, %458 : i32
cf.cond_br %459, ^bb61, ^bb62
^bb61:
%461 = llvm.load %456 : !llvm.ptr -> i32
%462 = arith.extsi %461 : i32 to i64
%463 = llvm.getelementptr %319[%462] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%460 = llvm.load %463 : !llvm.ptr -> i64
%464 = arith.remsi %460, %arg0 : i64
%465 = arith.constant 0 : i32
%467 = arith.extsi %465 : i32 to i64
%466 = arith.cmpi eq, %464, %467 : i64
cf.cond_br %466, ^bb63, ^bb64
^bb63:
%468 = llvm.load %456 : !llvm.ptr -> i32
%469 = arith.constant 1 : i32
%470 = arith.addi %468, %469 : i32
llvm.store %470, %456 : i32, !llvm.ptr
cf.br ^bb60
^bb64:
cf.br ^bb65
^bb65:
%472 = llvm.load %436 : !llvm.ptr -> i64
%471 = func.call @powmod(%464, %472, %arg0) : (i64, i64, i64) -> i64
%473 = llvm.mlir.constant(1 : i64) : i64
%474 = llvm.alloca %473 x i64 : (i64) -> !llvm.ptr
llvm.store %471, %474 : i64, !llvm.ptr
%475 = llvm.load %474 : !llvm.ptr -> i64
%476 = arith.constant 1 : i32
%478 = arith.extsi %476 : i32 to i64
%477 = arith.cmpi ne, %475, %478 : i64
%479 = scf.if %477 -> (i1) {
%480 = llvm.load %474 : !llvm.ptr -> i64
%481 = arith.constant 1 : i32
%483 = arith.extsi %481 : i32 to i64
%482 = arith.subi %arg0, %483 : i64
%484 = arith.cmpi ne, %480, %482 : i64
scf.yield %484 : i1
} else {
%485 = arith.constant false
scf.yield %485 : i1
}
cf.cond_br %479, ^bb66, ^bb67
^bb66:
%486 = arith.constant 0 : i32
%487 = llvm.mlir.constant(1 : i64) : i64
%488 = llvm.alloca %487 x i32 : (i64) -> !llvm.ptr
llvm.store %486, %488 : i32, !llvm.ptr
%489 = arith.constant 0 : i32
%490 = llvm.mlir.constant(1 : i64) : i64
%491 = llvm.alloca %490 x i32 : (i64) -> !llvm.ptr
llvm.store %489, %491 : i32, !llvm.ptr
cf.br ^bb69
^bb69:
%492 = llvm.load %491 : !llvm.ptr -> i32
%493 = llvm.load %439 : !llvm.ptr -> i32
%494 = arith.cmpi slt, %492, %493 : i32
cf.cond_br %494, ^bb70, ^bb71
^bb70:
%496 = llvm.load %474 : !llvm.ptr -> i64
%497 = llvm.load %474 : !llvm.ptr -> i64
%495 = func.call @mulmod(%496, %497, %arg0) : (i64, i64, i64) -> i64
llvm.store %495, %474 : i64, !llvm.ptr
%498 = llvm.load %474 : !llvm.ptr -> i64
%499 = arith.constant 1 : i32
%501 = arith.extsi %499 : i32 to i64
%500 = arith.cmpi eq, %498, %501 : i64
cf.cond_br %500, ^bb72, ^bb73
^bb72:
func.call @free(%319) : (!llvm.ptr) -> ()
%503 = arith.constant 0 : i32
func.return %503 : i32
^bb73:
cf.br ^bb74
^bb74:
%504 = llvm.load %474 : !llvm.ptr -> i64
%505 = arith.constant 1 : i32
%507 = arith.extsi %505 : i32 to i64
%506 = arith.subi %arg0, %507 : i64
%508 = arith.cmpi eq, %504, %506 : i64
cf.cond_br %508, ^bb75, ^bb76
^bb75:
%509 = arith.constant 1 : i32
llvm.store %509, %488 : i32, !llvm.ptr
cf.br ^bb71
^bb76:
cf.br ^bb77
^bb77:
%510 = llvm.load %491 : !llvm.ptr -> i32
%511 = arith.constant 1 : i32
%512 = arith.addi %510, %511 : i32
llvm.store %512, %491 : i32, !llvm.ptr
cf.br ^bb69
^bb71:
%513 = llvm.load %488 : !llvm.ptr -> i32
%514 = arith.constant 0 : i32
%515 = arith.cmpi eq, %513, %514 : i32
cf.cond_br %515, ^bb78, ^bb79
^bb78:
func.call @free(%319) : (!llvm.ptr) -> ()
%517 = arith.constant 0 : i32
func.return %517 : i32
^bb79:
cf.br ^bb80
^bb80:
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%518 = llvm.load %456 : !llvm.ptr -> i32
%519 = arith.constant 1 : i32
%520 = arith.addi %518, %519 : i32
llvm.store %520, %456 : i32, !llvm.ptr
cf.br ^bb60
^bb62:
func.call @free(%319) : (!llvm.ptr) -> ()
%522 = arith.constant 1 : i32
func.return %522 : i32
}
func.func @digit_sum(%arg0: i64) -> i64 {
%523 = llvm.mlir.constant(1 : i64) : i64
%524 = llvm.alloca %523 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %524 : i64, !llvm.ptr
%525 = arith.constant 0 : i32
%526 = arith.extsi %525 : i32 to i64
%527 = llvm.mlir.constant(1 : i64) : i64
%528 = llvm.alloca %527 x i64 : (i64) -> !llvm.ptr
llvm.store %526, %528 : i64, !llvm.ptr
cf.br ^bb81
^bb81:
%529 = llvm.load %524 : !llvm.ptr -> i64
%530 = arith.constant 10 : i32
%532 = arith.extsi %530 : i32 to i64
%531 = arith.cmpi sge, %529, %532 : i64
cf.cond_br %531, ^bb82, ^bb83
^bb82:
%533 = llvm.load %528 : !llvm.ptr -> i64
%534 = llvm.load %524 : !llvm.ptr -> i64
%535 = arith.constant 10 : i32
%537 = arith.extsi %535 : i32 to i64
%536 = arith.remsi %534, %537 : i64
%538 = arith.addi %533, %536 : i64
llvm.store %538, %528 : i64, !llvm.ptr
%539 = llvm.load %524 : !llvm.ptr -> i64
%540 = arith.constant 10 : i32
%542 = arith.extsi %540 : i32 to i64
%541 = arith.divsi %539, %542 : i64
llvm.store %541, %524 : i64, !llvm.ptr
cf.br ^bb81
^bb83:
%543 = llvm.load %528 : !llvm.ptr -> i64
%544 = llvm.load %524 : !llvm.ptr -> i64
%545 = arith.addi %543, %544 : i64
func.return %545 : i64
}
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func @main() -> i32 {
%546 = arith.constant 14 : i32
%547 = arith.constant 200000 : i32
%548 = arith.extsi %547 : i32 to i64
%550 = arith.constant 8 : i32
%551 = arith.extsi %550 : i32 to i64
%549 = func.call @calloc(%548, %551) : (i64, i64) -> !llvm.ptr
%553 = arith.constant 8 : i32
%554 = arith.extsi %553 : i32 to i64
%552 = func.call @calloc(%548, %554) : (i64, i64) -> !llvm.ptr
%556 = arith.constant 1 : i32
%557 = arith.extsi %556 : i32 to i64
%555 = func.call @calloc(%548, %557) : (i64, i64) -> !llvm.ptr
%559 = arith.constant 1 : i32
%560 = arith.extsi %559 : i32 to i64
%558 = func.call @calloc(%548, %560) : (i64, i64) -> !llvm.ptr
%561 = llvm.mlir.zero : !llvm.ptr
%562 = llvm.icmp "eq" %549, %561 : !llvm.ptr
%563 = scf.if %562 -> (i1) {
%564 = arith.constant true
scf.yield %564 : i1
} else {
%565 = llvm.mlir.zero : !llvm.ptr
%566 = llvm.icmp "eq" %552, %565 : !llvm.ptr
scf.yield %566 : i1
}
%567 = scf.if %563 -> (i1) {
%568 = arith.constant true
scf.yield %568 : i1
} else {
%569 = llvm.mlir.zero : !llvm.ptr
%570 = llvm.icmp "eq" %555, %569 : !llvm.ptr
scf.yield %570 : i1
}
%571 = scf.if %567 -> (i1) {
%572 = arith.constant true
scf.yield %572 : i1
} else {
%573 = llvm.mlir.zero : !llvm.ptr
%574 = llvm.icmp "eq" %558, %573 : !llvm.ptr
scf.yield %574 : i1
}
cf.cond_br %571, ^bb84, ^bb85
^bb84:
%575 = arith.constant 1 : i32
func.return %575 : i32
^bb85:
cf.br ^bb86
^bb86:
%576 = arith.constant 0 : i32
%577 = arith.extsi %576 : i32 to i64
%578 = llvm.mlir.constant(1 : i64) : i64
%579 = llvm.alloca %578 x i64 : (i64) -> !llvm.ptr
llvm.store %577, %579 : i64, !llvm.ptr
%580 = arith.constant 1 : i32
%581 = arith.extsi %580 : i32 to i64
%582 = llvm.mlir.constant(1 : i64) : i64
%583 = llvm.alloca %582 x i64 : (i64) -> !llvm.ptr
llvm.store %581, %583 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%584 = llvm.load %583 : !llvm.ptr -> i64
%585 = arith.constant 9 : i32
%587 = arith.extsi %585 : i32 to i64
%586 = arith.cmpi sle, %584, %587 : i64
cf.cond_br %586, ^bb88, ^bb89
^bb88:
%588 = llvm.load %583 : !llvm.ptr -> i64
%589 = llvm.load %579 : !llvm.ptr -> i64
%590 = llvm.getelementptr %549[%589] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %588, %590 : i64, !llvm.ptr
%591 = arith.constant 0 : i32
%592 = llvm.load %579 : !llvm.ptr -> i64
%593 = arith.trunci %591 : i32 to i8
%594 = llvm.getelementptr %555[%592] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %593, %594 : i8, !llvm.ptr
%595 = llvm.load %579 : !llvm.ptr -> i64
%596 = arith.constant 1 : i32
%598 = arith.extsi %596 : i32 to i64
%597 = arith.addi %595, %598 : i64
llvm.store %597, %579 : i64, !llvm.ptr
%599 = llvm.load %583 : !llvm.ptr -> i64
%600 = arith.constant 1 : i32
%602 = arith.extsi %600 : i32 to i64
%601 = arith.addi %599, %602 : i64
llvm.store %601, %583 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%603 = arith.constant 0 : i32
%604 = arith.extsi %603 : i32 to i64
%605 = llvm.mlir.constant(1 : i64) : i64
%606 = llvm.alloca %605 x i64 : (i64) -> !llvm.ptr
llvm.store %604, %606 : i64, !llvm.ptr
%607 = arith.constant 1 : i32
%608 = llvm.mlir.constant(1 : i64) : i64
%609 = llvm.alloca %608 x i32 : (i64) -> !llvm.ptr
llvm.store %607, %609 : i32, !llvm.ptr
cf.br ^bb90
^bb90:
%610 = llvm.load %609 : !llvm.ptr -> i32
%611 = arith.cmpi slt, %610, %546 : i32
cf.cond_br %611, ^bb91, ^bb92
^bb91:
%612 = llvm.load %609 : !llvm.ptr -> i32
%613 = arith.constant 1 : i32
%614 = arith.addi %612, %613 : i32
llvm.store %614, %609 : i32, !llvm.ptr
%615 = arith.constant 0 : i32
%616 = arith.extsi %615 : i32 to i64
%617 = llvm.mlir.constant(1 : i64) : i64
%618 = llvm.alloca %617 x i64 : (i64) -> !llvm.ptr
llvm.store %616, %618 : i64, !llvm.ptr
%619 = arith.constant 0 : i32
%620 = arith.extsi %619 : i32 to i64
%621 = llvm.mlir.constant(1 : i64) : i64
%622 = llvm.alloca %621 x i64 : (i64) -> !llvm.ptr
llvm.store %620, %622 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%623 = llvm.load %622 : !llvm.ptr -> i64
%624 = llvm.load %579 : !llvm.ptr -> i64
%625 = arith.cmpi slt, %623, %624 : i64
cf.cond_br %625, ^bb94, ^bb95
^bb94:
%627 = llvm.load %622 : !llvm.ptr -> i64
%628 = llvm.getelementptr %549[%627] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%626 = llvm.load %628 : !llvm.ptr -> i64
%630 = llvm.load %622 : !llvm.ptr -> i64
%631 = llvm.getelementptr %555[%630] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%629 = llvm.load %631 : !llvm.ptr -> i8
%632 = arith.extsi %629 : i8 to i32
%633 = arith.constant 0 : i32
%634 = arith.extsi %633 : i32 to i64
%635 = llvm.mlir.constant(1 : i64) : i64
%636 = llvm.alloca %635 x i64 : (i64) -> !llvm.ptr
llvm.store %634, %636 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%637 = llvm.load %636 : !llvm.ptr -> i64
%638 = arith.constant 9 : i32
%640 = arith.extsi %638 : i32 to i64
%639 = arith.cmpi sle, %637, %640 : i64
cf.cond_br %639, ^bb97, ^bb98
^bb97:
%641 = arith.constant 10 : i32
%643 = arith.extsi %641 : i32 to i64
%642 = arith.muli %626, %643 : i64
%644 = llvm.load %636 : !llvm.ptr -> i64
%645 = arith.addi %642, %644 : i64
%646 = arith.constant 1 : i32
%647 = arith.cmpi eq, %632, %646 : i32
cf.cond_br %647, ^bb99, ^bb100
^bb99:
%648 = func.call @is_prime(%645) : (i64) -> i32
%649 = arith.constant 1 : i32
%650 = arith.cmpi eq, %648, %649 : i32
cf.cond_br %650, ^bb102, ^bb103
^bb102:
%651 = llvm.load %606 : !llvm.ptr -> i64
%652 = arith.addi %651, %645 : i64
llvm.store %652, %606 : i64, !llvm.ptr
cf.br ^bb104
^bb103:
cf.br ^bb104
^bb104:
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
%653 = func.call @digit_sum(%645) : (i64) -> i64
%654 = arith.remsi %645, %653 : i64
%655 = arith.constant 0 : i32
%657 = arith.extsi %655 : i32 to i64
%656 = arith.cmpi eq, %654, %657 : i64
cf.cond_br %656, ^bb105, ^bb106
^bb105:
%658 = llvm.load %618 : !llvm.ptr -> i64
%659 = llvm.getelementptr %552[%658] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %645, %659 : i64, !llvm.ptr
%661 = arith.divsi %645, %653 : i64
%660 = func.call @is_prime(%661) : (i64) -> i32
%662 = arith.constant 1 : i32
%663 = arith.cmpi eq, %660, %662 : i32
cf.cond_br %663, ^bb108, ^bb109
^bb108:
%664 = arith.constant 1 : i32
%665 = llvm.load %618 : !llvm.ptr -> i64
%666 = arith.trunci %664 : i32 to i8
%667 = llvm.getelementptr %558[%665] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %666, %667 : i8, !llvm.ptr
cf.br ^bb110
^bb109:
%668 = arith.constant 0 : i32
%669 = llvm.load %618 : !llvm.ptr -> i64
%670 = arith.trunci %668 : i32 to i8
%671 = llvm.getelementptr %558[%669] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %670, %671 : i8, !llvm.ptr
cf.br ^bb110
^bb110:
%672 = llvm.load %618 : !llvm.ptr -> i64
%673 = arith.constant 1 : i32
%675 = arith.extsi %673 : i32 to i64
%674 = arith.addi %672, %675 : i64
llvm.store %674, %618 : i64, !llvm.ptr
%676 = llvm.load %618 : !llvm.ptr -> i64
%677 = arith.cmpi sge, %676, %548 : i64
cf.cond_br %677, ^bb111, ^bb112
^bb111:
%678 = llvm.mlir.addressof @str_0 : !llvm.ptr
%679 = llvm.call @printf(%678) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr) -> i32
%680 = arith.constant 1 : i32
func.return %680 : i32
^bb112:
cf.br ^bb113
^bb113:
cf.br ^bb107
^bb106:
cf.br ^bb107
^bb107:
%681 = llvm.load %636 : !llvm.ptr -> i64
%682 = arith.constant 1 : i32
%684 = arith.extsi %682 : i32 to i64
%683 = arith.addi %681, %684 : i64
llvm.store %683, %636 : i64, !llvm.ptr
cf.br ^bb96
^bb98:
%685 = llvm.load %622 : !llvm.ptr -> i64
%686 = arith.constant 1 : i32
%688 = arith.extsi %686 : i32 to i64
%687 = arith.addi %685, %688 : i64
llvm.store %687, %622 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%689 = arith.constant 0 : i32
%690 = arith.extsi %689 : i32 to i64
%691 = llvm.mlir.constant(1 : i64) : i64
%692 = llvm.alloca %691 x i64 : (i64) -> !llvm.ptr
llvm.store %690, %692 : i64, !llvm.ptr
cf.br ^bb114
^bb114:
%693 = llvm.load %692 : !llvm.ptr -> i64
%694 = llvm.load %618 : !llvm.ptr -> i64
%695 = arith.cmpi slt, %693, %694 : i64
cf.cond_br %695, ^bb115, ^bb116
^bb115:
%697 = llvm.load %692 : !llvm.ptr -> i64
%698 = llvm.getelementptr %552[%697] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%696 = llvm.load %698 : !llvm.ptr -> i64
%699 = llvm.load %692 : !llvm.ptr -> i64
%700 = llvm.getelementptr %549[%699] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %696, %700 : i64, !llvm.ptr
%702 = llvm.load %692 : !llvm.ptr -> i64
%703 = llvm.getelementptr %558[%702] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%701 = llvm.load %703 : !llvm.ptr -> i8
%704 = llvm.load %692 : !llvm.ptr -> i64
%705 = llvm.getelementptr %555[%704] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %701, %705 : i8, !llvm.ptr
%706 = llvm.load %692 : !llvm.ptr -> i64
%707 = arith.constant 1 : i32
%709 = arith.extsi %707 : i32 to i64
%708 = arith.addi %706, %709 : i64
llvm.store %708, %692 : i64, !llvm.ptr
cf.br ^bb114
^bb116:
%710 = llvm.load %618 : !llvm.ptr -> i64
llvm.store %710, %579 : i64, !llvm.ptr
cf.br ^bb90
^bb92:
%711 = llvm.mlir.addressof @str_1 : !llvm.ptr
%712 = llvm.load %606 : !llvm.ptr -> i64
%713 = llvm.call @printf(%711, %712) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%558) : (!llvm.ptr) -> ()
func.call @free(%555) : (!llvm.ptr) -> ()
func.call @free(%552) : (!llvm.ptr) -> ()
func.call @free(%549) : (!llvm.ptr) -> ()
%718 = arith.constant 0 : i32
func.return %718 : i32
}
}