Problem 545

Faulhaber's Formulas — 100000th k with D(k)=20010.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 545
# Faulhaber's Formulas — 100000th k with D(k)=20010.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
}

const L: i64 = 308
const TARGET: i64 = 100000
const LIMIT_N: i64 = 4000000

function isqrt(n: i64) -> i64 {
    if n <= 0 { return 0 }
    let mut x: i64 = n
    let mut y: i64 = (x + 1) / 2
    while y < x {
        x = y
        y = (x + n / x) / 2
    }
    return x
}

function gcd(a0: i64, b0: i64) -> i64 {
    let mut a: i64 = a0
    let mut b: i64 = b0
    while b != 0 {
        let t: i64 = a % b
        a = b
        b = t
    }
    return a
}

# Miller-Rabin primality (deterministic for n < 2^32 via bases 2,7,61).
# Replaces trial division which was O(sqrt(n)) per survivor.
function mulmod_pp(a: i64, b: i64, m: i64) -> i64 {
    return (a * b) % m
}

function powmod_pp(a0: i64, e0: i64, m: i64) -> i64 {
    let mut r: i64 = 1
    let mut a: i64 = a0 % m
    let mut e: i64 = e0
    while e > 0 {
        if (e & 1) != 0 { r = mulmod_pp(r, a, m) }
        a = mulmod_pp(a, a, m)
        e = e >> 1
    }
    return r
}

function mr_witness(n: i64, d: i64, s: i64, a0: i64) -> i32 {
    let a: i64 = a0 % n
    if a == 0 { return 1 }
    let mut x: i64 = powmod_pp(a, d, n)
    if x == 1 { return 1 }
    if x == n - 1 { return 1 }
    let mut j: i64 = 0
    while j < s - 1 {
        x = mulmod_pp(x, x, n)
        if x == n - 1 { return 1 }
        j = j + 1
    }
    return 0
}

function is_prime_small(n: i64) -> i32 {
    if n < 2 { return 0 }
    if n == 2 { return 1 }
    if n == 3 { return 1 }
    if n == 5 { return 1 }
    if n == 7 { return 1 }
    if n == 61 { return 1 }
    if (n & 1) == 0 { return 0 }
    if n % 3 == 0 { return 0 }
    if n % 5 == 0 { return 0 }
    if n % 7 == 0 { return 0 }
    if n % 61 == 0 { return 0 }
    let mut d: i64 = n - 1
    let mut s: i64 = 0
    while (d & 1) == 0 { d = d >> 1; s = s + 1 }
    if mr_witness(n, d, s, 2) == 0 { return 0 }
    if mr_witness(n, d, s, 7) == 0 { return 0 }
    if mr_witness(n, d, s, 61) == 0 { return 0 }
    return 1
}

function inv_mod(a0: i64, mod: i64) -> i64 {
    let mut a: i64 = a0 % mod
    if a < 0 { a = a + mod }
    let mut t: i64 = 0
    let mut newt: i64 = 1
    let mut r: i64 = mod
    let mut newr: i64 = a
    while newr != 0 {
        let q: i64 = r / newr
        let tt: i64 = newt
        newt = t - q * newt
        t = tt
        let rr: i64 = newr
        newr = r - q * newr
        r = rr
    }
    if r != 1 { return 0 }
    if t < 0 { t = t + mod }
    return t
}

function main() -> i32 {
    let invalid: ptr<i8> = calloc(LIMIT_N + 1, 1)
    let isprime_m: ptr<i8> = calloc(LIMIT_N + 1, 1)
    let small_primes: ptr<i64> = calloc(10000, 8)
    if invalid == null || isprime_m == null || small_primes == null { return 1 }
    invalid[0] = 1
    let mut nsp: i64 = 0
    let mut p: i64 = 2
    while p <= 10000 {
        if is_prime_small(p) == 1 {
            small_primes[nsp] = p
            nsp = nsp + 1
        }
        p = p + 1
    }
    let g_divs: ptr<i64> = calloc(32, 8)
    let mut nd: i64 = 0
    let mut d: i64 = 1
    while d * d <= L {
        if L % d == 0 {
            g_divs[nd] = d
            nd = nd + 1
            if d * d != L {
                g_divs[nd] = L / d
                nd = nd + 1
            }
        }
        d = d + 1
    }
    let mut gi: i64 = 0
    while gi < nd {
        let g: i64 = g_divs[gi]
        let b: i64 = L / g
        let mut m: i64 = 0
        while m <= LIMIT_N {
            isprime_m[m] = 1
            m = m + 1
        }
        isprime_m[0] = 0
        let p_max: i64 = g * LIMIT_N + 1
        let lim: i64 = isqrt(p_max)
        let mut qi: i64 = 0
        while qi < nsp {
            let q: i64 = small_primes[qi]
            if q > lim { break }
            if g % q == 0 {
                qi = qi + 1
                continue
            }
            let inv: i64 = inv_mod(g, q)
            let mut m0: i64 = (q - inv) % q
            if m0 == 0 { m0 = q }
            if g * m0 + 1 == q { m0 = m0 + q }
            if m0 <= LIMIT_N {
                let mut mm: i64 = m0
                while mm <= LIMIT_N {
                    isprime_m[mm] = 0
                    mm = mm + q
                }
            }
            qi = qi + 1
        }
        m = 1
        while m <= LIMIT_N {
            if isprime_m[m] == 1 {
                let pp: i64 = g * m + 1
                if pp != 2 && pp != 3 && pp != 5 && pp != 23 && pp != 29 {
                    if is_prime_small(pp) == 1 {
                        let f: i64 = m / gcd(m, b)
                        if f > 1 && invalid[f] == 0 {
                            let mut ff: i64 = f
                            while ff <= LIMIT_N {
                                invalid[ff] = 1
                                ff = ff + f
                            }
                        }
                    }
                }
            }
            m = m + 1
        }
        gi = gi + 1
    }
    let mut count: i64 = 0
    let mut ans: i64 = 0
    let mut nn: i64 = 1
    while nn <= LIMIT_N {
        if invalid[nn] == 0 {
            count = count + 1
            if count == TARGET {
                ans = L * nn
                break
            }
        }
        nn = nn + 1
    }
    printf("%lld\n", ans)
    free(invalid); free(isprime_m); free(small_primes); free(g_divs)
    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 isqrt_i64(int64_t n);
int64_t gcd_i64_i64(int64_t a0, int64_t b0);
int64_t mulmod_pp_i64_i64_i64(int64_t a, int64_t b, int64_t m);
int64_t powmod_pp_i64_i64_i64(int64_t a0, int64_t e0, int64_t m);
int32_t mr_witness_i64_i64_i64_i64(int64_t n, int64_t d, int64_t s, int64_t a0);
int32_t is_prime_small_i64(int64_t n);
int64_t inv_mod_i64_i64(int64_t a0, int64_t mod);
int32_t main(void);

static const int64_t L = 308;
static const int64_t TARGET = 100000;
static const int64_t LIMIT_N = 4000000;



int64_t isqrt_i64(int64_t n) {
    if (n <= 0) {
        return 0;
    }
    int64_t x = n;
    int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
    while (y < x) {
        x = y;
        y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
    }
    return x;
}

int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
    int64_t a = a0;
    int64_t b = b0;
    while (b != 0) {
        int64_t t = FLOW_CHECKED_MOD((a), (b));
        a = b;
        b = t;
    }
    return a;
}

int64_t mulmod_pp_i64_i64_i64(int64_t a, int64_t b, int64_t m) {
    return FLOW_CHECKED_MOD(((a * b)), (m));
}

int64_t powmod_pp_i64_i64_i64(int64_t a0, int64_t e0, int64_t m) {
    int64_t r = 1;
    int64_t a = FLOW_CHECKED_MOD((a0), (m));
    int64_t e = e0;
    while (e > 0) {
        if ((e & 1) != 0) {
            r = mulmod_pp_i64_i64_i64(r, a, m);
        }
        a = mulmod_pp_i64_i64_i64(a, a, m);
        e = FLOW_CHECKED_SHR((e), (1));
    }
    return r;
}

int32_t mr_witness_i64_i64_i64_i64(int64_t n, int64_t d, int64_t s, int64_t a0) {
    int64_t a = FLOW_CHECKED_MOD((a0), (n));
    if (a == 0) {
        return 1;
    }
    int64_t x = powmod_pp_i64_i64_i64(a, d, n);
    if (x == 1) {
        return 1;
    }
    if (x == (n - 1)) {
        return 1;
    }
    int64_t j = 0;
    while (j < (s - 1)) {
        x = mulmod_pp_i64_i64_i64(x, x, n);
        if (x == (n - 1)) {
            return 1;
        }
        j = (j + 1);
    }
    return 0;
}

int32_t is_prime_small_i64(int64_t n) {
    if (n < 2) {
        return 0;
    }
    if (n == 2) {
        return 1;
    }
    if (n == 3) {
        return 1;
    }
    if (n == 5) {
        return 1;
    }
    if (n == 7) {
        return 1;
    }
    if (n == 61) {
        return 1;
    }
    if ((n & 1) == 0) {
        return 0;
    }
    if (FLOW_CHECKED_MOD((n), (3)) == 0) {
        return 0;
    }
    if (FLOW_CHECKED_MOD((n), (5)) == 0) {
        return 0;
    }
    if (FLOW_CHECKED_MOD((n), (7)) == 0) {
        return 0;
    }
    if (FLOW_CHECKED_MOD((n), (61)) == 0) {
        return 0;
    }
    int64_t d = (n - 1);
    int64_t s = 0;
    while ((d & 1) == 0) {
        d = FLOW_CHECKED_SHR((d), (1));
        s = (s + 1);
    }
    if (mr_witness_i64_i64_i64_i64(n, d, s, 2) == 0) {
        return 0;
    }
    if (mr_witness_i64_i64_i64_i64(n, d, s, 7) == 0) {
        return 0;
    }
    if (mr_witness_i64_i64_i64_i64(n, d, s, 61) == 0) {
        return 0;
    }
    return 1;
}

int64_t inv_mod_i64_i64(int64_t a0, int64_t mod) {
    int64_t a = FLOW_CHECKED_MOD((a0), (mod));
    if (a < 0) {
        a = (a + mod);
    }
    int64_t t = 0;
    int64_t newt = 1;
    int64_t r = mod;
    int64_t newr = a;
    while (newr != 0) {
        int64_t q = FLOW_CHECKED_DIV((r), (newr));
        int64_t tt = newt;
        newt = (t - (q * newt));
        t = tt;
        int64_t rr = newr;
        newr = (r - (q * newr));
        r = rr;
    }
    if (r != 1) {
        return 0;
    }
    if (t < 0) {
        t = (t + mod);
    }
    return t;
}

int32_t main(void) {
    int8_t* invalid = (int8_t*)(calloc((LIMIT_N + 1), 1));
    int8_t* isprime_m = (int8_t*)(calloc((LIMIT_N + 1), 1));
    int64_t* small_primes = (int64_t*)(calloc(10000, 8));
    if (((invalid == NULL || isprime_m == NULL) || small_primes == NULL)) {
        return 1;
    }
    invalid[0] = 1;
    int64_t nsp = 0;
    int64_t p = 2;
    while (p <= 10000) {
        if (is_prime_small_i64(p) == 1) {
            small_primes[nsp] = p;
            nsp = (nsp + 1);
        }
        p = (p + 1);
    }
    int64_t* g_divs = (int64_t*)(calloc(32, 8));
    int64_t nd = 0;
    int64_t d = 1;
    while ((d * d) <= L) {
        if (FLOW_CHECKED_MOD((L), (d)) == 0) {
            g_divs[nd] = d;
            nd = (nd + 1);
            if ((d * d) != L) {
                g_divs[nd] = FLOW_CHECKED_DIV((L), (d));
                nd = (nd + 1);
            }
        }
        d = (d + 1);
    }
    int64_t gi = 0;
    while (gi < nd) {
        int64_t g = g_divs[gi];
        int64_t b = FLOW_CHECKED_DIV((L), (g));
        int64_t m = 0;
        while (m <= LIMIT_N) {
            isprime_m[m] = 1;
            m = (m + 1);
        }
        isprime_m[0] = 0;
        int64_t p_max = ((g * LIMIT_N) + 1);
        int64_t lim = isqrt_i64(p_max);
        int64_t qi = 0;
        while (qi < nsp) {
            int64_t q = small_primes[qi];
            if (q > lim) {
                break;
            }
            if (FLOW_CHECKED_MOD((g), (q)) == 0) {
                qi = (qi + 1);
                continue;
            }
            int64_t inv = inv_mod_i64_i64(g, q);
            int64_t m0 = FLOW_CHECKED_MOD(((q - inv)), (q));
            if (m0 == 0) {
                m0 = q;
            }
            if (((g * m0) + 1) == q) {
                m0 = (m0 + q);
            }
            if (m0 <= LIMIT_N) {
                int64_t mm = m0;
                while (mm <= LIMIT_N) {
                    isprime_m[mm] = 0;
                    mm = (mm + q);
                }
            }
            qi = (qi + 1);
        }
        m = 1;
        while (m <= LIMIT_N) {
            if (isprime_m[m] == 1) {
                int64_t pp = ((g * m) + 1);
                if (((((pp != 2 && pp != 3) && pp != 5) && pp != 23) && pp != 29)) {
                    if (is_prime_small_i64(pp) == 1) {
                        int64_t f = FLOW_CHECKED_DIV((m), (gcd_i64_i64(m, b)));
                        if ((f > 1 && invalid[f] == 0)) {
                            int64_t ff = f;
                            while (ff <= LIMIT_N) {
                                invalid[ff] = 1;
                                ff = (ff + f);
                            }
                        }
                    }
                }
            }
            m = (m + 1);
        }
        gi = (gi + 1);
    }
    int64_t count = 0;
    int64_t ans = 0;
    int64_t nn = 1;
    while (nn <= LIMIT_N) {
        if (invalid[nn] == 0) {
            count = (count + 1);
            if (count == TARGET) {
                ans = (L * nn);
                break;
            }
        }
        nn = (nn + 1);
    }
    printf("%lld\n", ans);
    free(invalid);
    free(isprime_m);
    free(small_primes);
    free(g_divs);
    return 0;
}

Generated MLIR

module {
  llvm.func @printf(!llvm.ptr, ...) -> i32
  llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
  func.func private @calloc(i64, i64) -> !llvm.ptr
  func.func private @free(!llvm.ptr) -> ()
  // Constant: L
  llvm.mlir.global internal constant @L(308 : i64) : i64
  // Constant: TARGET
  llvm.mlir.global internal constant @TARGET(100000 : i64) : i64
  // Constant: LIMIT_N
  llvm.mlir.global internal constant @LIMIT_N(4000000 : i64) : i64
  func.func @isqrt(%arg0: i64) -> i64 {
    %0 = arith.constant 0 : i32
    %2 = arith.extsi %0 : i32 to i64
    %1 = arith.cmpi sle, %arg0, %2 : i64
    cf.cond_br %1, ^bb0, ^bb1
    ^bb0:
      %3 = arith.constant 0 : i32
      %4 = arith.extsi %3 : i32 to i64
      func.return %4 : i64
    ^bb1:
      cf.br ^bb2
    ^bb2:
    %5 = llvm.mlir.constant(1 : i64) : i64
    %6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %6 : i64, !llvm.ptr
    %7 = llvm.load %6 : !llvm.ptr -> i64
    %8 = arith.constant 1 : i32
    %10 = arith.extsi %8 : i32 to i64
    %9 = arith.addi %7, %10 : i64
    %11 = arith.constant 2 : i32
    %13 = arith.extsi %11 : i32 to i64
    %12 = arith.divsi %9, %13 : i64
    %14 = llvm.mlir.constant(1 : i64) : i64
    %15 = llvm.alloca %14 x i64 : (i64) -> !llvm.ptr
    llvm.store %12, %15 : i64, !llvm.ptr
    cf.br ^bb3
    ^bb3:
    %16 = llvm.load %15 : !llvm.ptr -> i64
    %17 = llvm.load %6 : !llvm.ptr -> i64
    %18 = arith.cmpi slt, %16, %17 : i64
    cf.cond_br %18, ^bb4, ^bb5
    ^bb4:
      %19 = llvm.load %15 : !llvm.ptr -> i64
      llvm.store %19, %6 : i64, !llvm.ptr
      %20 = llvm.load %6 : !llvm.ptr -> i64
      %21 = llvm.load %6 : !llvm.ptr -> i64
      %22 = arith.divsi %arg0, %21 : i64
      %23 = arith.addi %20, %22 : i64
      %24 = arith.constant 2 : i32
      %26 = arith.extsi %24 : i32 to i64
      %25 = arith.divsi %23, %26 : i64
      llvm.store %25, %15 : i64, !llvm.ptr
      cf.br ^bb3
    ^bb5:
    %27 = llvm.load %6 : !llvm.ptr -> i64
    func.return %27 : i64
  }
  func.func @gcd(%arg0: i64, %arg1: i64) -> i64 {
    %28 = llvm.mlir.constant(1 : i64) : i64
    %29 = llvm.alloca %28 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %29 : i64, !llvm.ptr
    %30 = llvm.mlir.constant(1 : i64) : i64
    %31 = llvm.alloca %30 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %31 : i64, !llvm.ptr
    cf.br ^bb6
    ^bb6:
    %32 = llvm.load %31 : !llvm.ptr -> i64
    %33 = arith.constant 0 : i32
    %35 = arith.extsi %33 : i32 to i64
    %34 = arith.cmpi ne, %32, %35 : i64
    cf.cond_br %34, ^bb7, ^bb8
    ^bb7:
      %36 = llvm.load %29 : !llvm.ptr -> i64
      %37 = llvm.load %31 : !llvm.ptr -> i64
      %38 = arith.remsi %36, %37 : i64
      %39 = llvm.load %31 : !llvm.ptr -> i64
      llvm.store %39, %29 : i64, !llvm.ptr
      llvm.store %38, %31 : i64, !llvm.ptr
      cf.br ^bb6
    ^bb8:
    %40 = llvm.load %29 : !llvm.ptr -> i64
    func.return %40 : i64
  }
  func.func @mulmod_pp(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %41 = arith.muli %arg0, %arg1 : i64
    %42 = arith.remsi %41, %arg2 : i64
    func.return %42 : i64
  }
  func.func @powmod_pp(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
    %43 = arith.constant 1 : i32
    %44 = arith.extsi %43 : i32 to i64
    %45 = llvm.mlir.constant(1 : i64) : i64
    %46 = llvm.alloca %45 x i64 : (i64) -> !llvm.ptr
    llvm.store %44, %46 : i64, !llvm.ptr
    %47 = arith.remsi %arg0, %arg2 : i64
    %48 = llvm.mlir.constant(1 : i64) : i64
    %49 = llvm.alloca %48 x i64 : (i64) -> !llvm.ptr
    llvm.store %47, %49 : i64, !llvm.ptr
    %50 = llvm.mlir.constant(1 : i64) : i64
    %51 = llvm.alloca %50 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %51 : i64, !llvm.ptr
    cf.br ^bb9
    ^bb9:
    %52 = llvm.load %51 : !llvm.ptr -> i64
    %53 = arith.constant 0 : i32
    %55 = arith.extsi %53 : i32 to i64
    %54 = arith.cmpi sgt, %52, %55 : i64
    cf.cond_br %54, ^bb10, ^bb11
    ^bb10:
      %56 = llvm.load %51 : !llvm.ptr -> i64
      %57 = arith.constant 1 : i32
      %59 = arith.extsi %57 : i32 to i64
      %58 = arith.andi %56, %59 : i64
      %60 = arith.constant 0 : i32
      %62 = arith.extsi %60 : i32 to i64
      %61 = arith.cmpi ne, %58, %62 : i64
      cf.cond_br %61, ^bb12, ^bb13
      ^bb12:
        %64 = llvm.load %46 : !llvm.ptr -> i64
        %65 = llvm.load %49 : !llvm.ptr -> i64
        %63 = func.call @mulmod_pp(%64, %65, %arg2) : (i64, i64, i64) -> i64
        llvm.store %63, %46 : i64, !llvm.ptr
        cf.br ^bb14
      ^bb13:
        cf.br ^bb14
      ^bb14:
      %67 = llvm.load %49 : !llvm.ptr -> i64
      %68 = llvm.load %49 : !llvm.ptr -> i64
      %66 = func.call @mulmod_pp(%67, %68, %arg2) : (i64, i64, i64) -> i64
      llvm.store %66, %49 : i64, !llvm.ptr
      %69 = llvm.load %51 : !llvm.ptr -> i64
      %70 = arith.constant 1 : i32
      %72 = arith.extsi %70 : i32 to i64
      %71 = arith.shrsi %69, %72 : i64
      llvm.store %71, %51 : i64, !llvm.ptr
      cf.br ^bb9
    ^bb11:
    %73 = llvm.load %46 : !llvm.ptr -> i64
    func.return %73 : i64
  }
  func.func @mr_witness(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> i32 {
    %74 = arith.remsi %arg3, %arg0 : i64
    %75 = arith.constant 0 : i32
    %77 = arith.extsi %75 : i32 to i64
    %76 = arith.cmpi eq, %74, %77 : i64
    cf.cond_br %76, ^bb15, ^bb16
    ^bb15:
      %78 = arith.constant 1 : i32
      func.return %78 : i32
    ^bb16:
      cf.br ^bb17
    ^bb17:
    %79 = func.call @powmod_pp(%74, %arg1, %arg0) : (i64, i64, i64) -> i64
    %80 = llvm.mlir.constant(1 : i64) : i64
    %81 = llvm.alloca %80 x i64 : (i64) -> !llvm.ptr
    llvm.store %79, %81 : i64, !llvm.ptr
    %82 = llvm.load %81 : !llvm.ptr -> i64
    %83 = arith.constant 1 : i32
    %85 = arith.extsi %83 : i32 to i64
    %84 = arith.cmpi eq, %82, %85 : i64
    cf.cond_br %84, ^bb18, ^bb19
    ^bb18:
      %86 = arith.constant 1 : i32
      func.return %86 : i32
    ^bb19:
      cf.br ^bb20
    ^bb20:
    %87 = llvm.load %81 : !llvm.ptr -> i64
    %88 = arith.constant 1 : i32
    %90 = arith.extsi %88 : i32 to i64
    %89 = arith.subi %arg0, %90 : i64
    %91 = arith.cmpi eq, %87, %89 : i64
    cf.cond_br %91, ^bb21, ^bb22
    ^bb21:
      %92 = arith.constant 1 : i32
      func.return %92 : i32
    ^bb22:
      cf.br ^bb23
    ^bb23:
    %93 = arith.constant 0 : i32
    %94 = arith.extsi %93 : i32 to i64
    %95 = llvm.mlir.constant(1 : i64) : i64
    %96 = llvm.alloca %95 x i64 : (i64) -> !llvm.ptr
    llvm.store %94, %96 : i64, !llvm.ptr
    cf.br ^bb24
    ^bb24:
    %97 = llvm.load %96 : !llvm.ptr -> i64
    %98 = arith.constant 1 : i32
    %100 = arith.extsi %98 : i32 to i64
    %99 = arith.subi %arg2, %100 : i64
    %101 = arith.cmpi slt, %97, %99 : i64
    cf.cond_br %101, ^bb25, ^bb26
    ^bb25:
      %103 = llvm.load %81 : !llvm.ptr -> i64
      %104 = llvm.load %81 : !llvm.ptr -> i64
      %102 = func.call @mulmod_pp(%103, %104, %arg0) : (i64, i64, i64) -> i64
      llvm.store %102, %81 : i64, !llvm.ptr
      %105 = llvm.load %81 : !llvm.ptr -> i64
      %106 = arith.constant 1 : i32
      %108 = arith.extsi %106 : i32 to i64
      %107 = arith.subi %arg0, %108 : i64
      %109 = arith.cmpi eq, %105, %107 : i64
      cf.cond_br %109, ^bb27, ^bb28
      ^bb27:
        %110 = arith.constant 1 : i32
        func.return %110 : i32
      ^bb28:
        cf.br ^bb29
      ^bb29:
      %111 = llvm.load %96 : !llvm.ptr -> i64
      %112 = arith.constant 1 : i32
      %114 = arith.extsi %112 : i32 to i64
      %113 = arith.addi %111, %114 : i64
      llvm.store %113, %96 : i64, !llvm.ptr
      cf.br ^bb24
    ^bb26:
    %115 = arith.constant 0 : i32
    func.return %115 : i32
  }
  func.func @is_prime_small(%arg0: i64) -> i32 {
    %116 = arith.constant 2 : i32
    %118 = arith.extsi %116 : i32 to i64
    %117 = arith.cmpi slt, %arg0, %118 : i64
    cf.cond_br %117, ^bb30, ^bb31
    ^bb30:
      %119 = arith.constant 0 : i32
      func.return %119 : i32
    ^bb31:
      cf.br ^bb32
    ^bb32:
    %120 = arith.constant 2 : i32
    %122 = arith.extsi %120 : i32 to i64
    %121 = arith.cmpi eq, %arg0, %122 : i64
    cf.cond_br %121, ^bb33, ^bb34
    ^bb33:
      %123 = arith.constant 1 : i32
      func.return %123 : i32
    ^bb34:
      cf.br ^bb35
    ^bb35:
    %124 = arith.constant 3 : i32
    %126 = arith.extsi %124 : i32 to i64
    %125 = arith.cmpi eq, %arg0, %126 : i64
    cf.cond_br %125, ^bb36, ^bb37
    ^bb36:
      %127 = arith.constant 1 : i32
      func.return %127 : i32
    ^bb37:
      cf.br ^bb38
    ^bb38:
    %128 = arith.constant 5 : i32
    %130 = arith.extsi %128 : i32 to i64
    %129 = arith.cmpi eq, %arg0, %130 : i64
    cf.cond_br %129, ^bb39, ^bb40
    ^bb39:
      %131 = arith.constant 1 : i32
      func.return %131 : i32
    ^bb40:
      cf.br ^bb41
    ^bb41:
    %132 = arith.constant 7 : i32
    %134 = arith.extsi %132 : i32 to i64
    %133 = arith.cmpi eq, %arg0, %134 : i64
    cf.cond_br %133, ^bb42, ^bb43
    ^bb42:
      %135 = arith.constant 1 : i32
      func.return %135 : i32
    ^bb43:
      cf.br ^bb44
    ^bb44:
    %136 = arith.constant 61 : i32
    %138 = arith.extsi %136 : i32 to i64
    %137 = arith.cmpi eq, %arg0, %138 : i64
    cf.cond_br %137, ^bb45, ^bb46
    ^bb45:
      %139 = arith.constant 1 : i32
      func.return %139 : i32
    ^bb46:
      cf.br ^bb47
    ^bb47:
    %140 = arith.constant 1 : i32
    %142 = arith.extsi %140 : i32 to i64
    %141 = arith.andi %arg0, %142 : i64
    %143 = arith.constant 0 : i32
    %145 = arith.extsi %143 : i32 to i64
    %144 = arith.cmpi eq, %141, %145 : i64
    cf.cond_br %144, ^bb48, ^bb49
    ^bb48:
      %146 = arith.constant 0 : i32
      func.return %146 : i32
    ^bb49:
      cf.br ^bb50
    ^bb50:
    %147 = arith.constant 3 : i32
    %149 = arith.extsi %147 : i32 to i64
    %148 = arith.remsi %arg0, %149 : i64
    %150 = arith.constant 0 : i32
    %152 = arith.extsi %150 : i32 to i64
    %151 = arith.cmpi eq, %148, %152 : i64
    cf.cond_br %151, ^bb51, ^bb52
    ^bb51:
      %153 = arith.constant 0 : i32
      func.return %153 : i32
    ^bb52:
      cf.br ^bb53
    ^bb53:
    %154 = arith.constant 5 : i32
    %156 = arith.extsi %154 : i32 to i64
    %155 = arith.remsi %arg0, %156 : i64
    %157 = arith.constant 0 : i32
    %159 = arith.extsi %157 : i32 to i64
    %158 = arith.cmpi eq, %155, %159 : i64
    cf.cond_br %158, ^bb54, ^bb55
    ^bb54:
      %160 = arith.constant 0 : i32
      func.return %160 : i32
    ^bb55:
      cf.br ^bb56
    ^bb56:
    %161 = arith.constant 7 : i32
    %163 = arith.extsi %161 : i32 to i64
    %162 = arith.remsi %arg0, %163 : i64
    %164 = arith.constant 0 : i32
    %166 = arith.extsi %164 : i32 to i64
    %165 = arith.cmpi eq, %162, %166 : i64
    cf.cond_br %165, ^bb57, ^bb58
    ^bb57:
      %167 = arith.constant 0 : i32
      func.return %167 : i32
    ^bb58:
      cf.br ^bb59
    ^bb59:
    %168 = arith.constant 61 : i32
    %170 = arith.extsi %168 : i32 to i64
    %169 = arith.remsi %arg0, %170 : i64
    %171 = arith.constant 0 : i32
    %173 = arith.extsi %171 : i32 to i64
    %172 = arith.cmpi eq, %169, %173 : i64
    cf.cond_br %172, ^bb60, ^bb61
    ^bb60:
      %174 = arith.constant 0 : i32
      func.return %174 : i32
    ^bb61:
      cf.br ^bb62
    ^bb62:
    %175 = arith.constant 1 : i32
    %177 = arith.extsi %175 : i32 to i64
    %176 = arith.subi %arg0, %177 : i64
    %178 = llvm.mlir.constant(1 : i64) : i64
    %179 = llvm.alloca %178 x i64 : (i64) -> !llvm.ptr
    llvm.store %176, %179 : i64, !llvm.ptr
    %180 = arith.constant 0 : i32
    %181 = arith.extsi %180 : i32 to i64
    %182 = llvm.mlir.constant(1 : i64) : i64
    %183 = llvm.alloca %182 x i64 : (i64) -> !llvm.ptr
    llvm.store %181, %183 : i64, !llvm.ptr
    cf.br ^bb63
    ^bb63:
    %184 = llvm.load %179 : !llvm.ptr -> i64
    %185 = arith.constant 1 : i32
    %187 = arith.extsi %185 : i32 to i64
    %186 = arith.andi %184, %187 : i64
    %188 = arith.constant 0 : i32
    %190 = arith.extsi %188 : i32 to i64
    %189 = arith.cmpi eq, %186, %190 : i64
    cf.cond_br %189, ^bb64, ^bb65
    ^bb64:
      %191 = llvm.load %179 : !llvm.ptr -> i64
      %192 = arith.constant 1 : i32
      %194 = arith.extsi %192 : i32 to i64
      %193 = arith.shrsi %191, %194 : i64
      llvm.store %193, %179 : i64, !llvm.ptr
      %195 = llvm.load %183 : !llvm.ptr -> i64
      %196 = arith.constant 1 : i32
      %198 = arith.extsi %196 : i32 to i64
      %197 = arith.addi %195, %198 : i64
      llvm.store %197, %183 : i64, !llvm.ptr
      cf.br ^bb63
    ^bb65:
    %200 = llvm.load %179 : !llvm.ptr -> i64
    %201 = llvm.load %183 : !llvm.ptr -> i64
    %202 = arith.constant 2 : i32
    %203 = arith.extsi %202 : i32 to i64
    %199 = func.call @mr_witness(%arg0, %200, %201, %203) : (i64, i64, i64, i64) -> i32
    %204 = arith.constant 0 : i32
    %205 = arith.cmpi eq, %199, %204 : i32
    cf.cond_br %205, ^bb66, ^bb67
    ^bb66:
      %206 = arith.constant 0 : i32
      func.return %206 : i32
    ^bb67:
      cf.br ^bb68
    ^bb68:
    %208 = llvm.load %179 : !llvm.ptr -> i64
    %209 = llvm.load %183 : !llvm.ptr -> i64
    %210 = arith.constant 7 : i32
    %211 = arith.extsi %210 : i32 to i64
    %207 = func.call @mr_witness(%arg0, %208, %209, %211) : (i64, i64, i64, i64) -> i32
    %212 = arith.constant 0 : i32
    %213 = arith.cmpi eq, %207, %212 : i32
    cf.cond_br %213, ^bb69, ^bb70
    ^bb69:
      %214 = arith.constant 0 : i32
      func.return %214 : i32
    ^bb70:
      cf.br ^bb71
    ^bb71:
    %216 = llvm.load %179 : !llvm.ptr -> i64
    %217 = llvm.load %183 : !llvm.ptr -> i64
    %218 = arith.constant 61 : i32
    %219 = arith.extsi %218 : i32 to i64
    %215 = func.call @mr_witness(%arg0, %216, %217, %219) : (i64, i64, i64, i64) -> i32
    %220 = arith.constant 0 : i32
    %221 = arith.cmpi eq, %215, %220 : i32
    cf.cond_br %221, ^bb72, ^bb73
    ^bb72:
      %222 = arith.constant 0 : i32
      func.return %222 : i32
    ^bb73:
      cf.br ^bb74
    ^bb74:
    %223 = arith.constant 1 : i32
    func.return %223 : i32
  }
  func.func @inv_mod(%arg0: i64, %arg1: i64) -> i64 {
    %224 = arith.remsi %arg0, %arg1 : i64
    %225 = llvm.mlir.constant(1 : i64) : i64
    %226 = llvm.alloca %225 x i64 : (i64) -> !llvm.ptr
    llvm.store %224, %226 : i64, !llvm.ptr
    %227 = llvm.load %226 : !llvm.ptr -> i64
    %228 = arith.constant 0 : i32
    %230 = arith.extsi %228 : i32 to i64
    %229 = arith.cmpi slt, %227, %230 : i64
    cf.cond_br %229, ^bb75, ^bb76
    ^bb75:
      %231 = llvm.load %226 : !llvm.ptr -> i64
      %232 = arith.addi %231, %arg1 : i64
      llvm.store %232, %226 : i64, !llvm.ptr
      cf.br ^bb77
    ^bb76:
      cf.br ^bb77
    ^bb77:
    %233 = arith.constant 0 : i32
    %234 = arith.extsi %233 : i32 to i64
    %235 = llvm.mlir.constant(1 : i64) : i64
    %236 = llvm.alloca %235 x i64 : (i64) -> !llvm.ptr
    llvm.store %234, %236 : i64, !llvm.ptr
    %237 = arith.constant 1 : i32
    %238 = arith.extsi %237 : i32 to i64
    %239 = llvm.mlir.constant(1 : i64) : i64
    %240 = llvm.alloca %239 x i64 : (i64) -> !llvm.ptr
    llvm.store %238, %240 : i64, !llvm.ptr
    %241 = llvm.mlir.constant(1 : i64) : i64
    %242 = llvm.alloca %241 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %242 : i64, !llvm.ptr
    %243 = llvm.load %226 : !llvm.ptr -> i64
    %244 = llvm.mlir.constant(1 : i64) : i64
    %245 = llvm.alloca %244 x i64 : (i64) -> !llvm.ptr
    llvm.store %243, %245 : i64, !llvm.ptr
    cf.br ^bb78
    ^bb78:
    %246 = llvm.load %245 : !llvm.ptr -> i64
    %247 = arith.constant 0 : i32
    %249 = arith.extsi %247 : i32 to i64
    %248 = arith.cmpi ne, %246, %249 : i64
    cf.cond_br %248, ^bb79, ^bb80
    ^bb79:
      %250 = llvm.load %242 : !llvm.ptr -> i64
      %251 = llvm.load %245 : !llvm.ptr -> i64
      %252 = arith.divsi %250, %251 : i64
      %253 = llvm.load %240 : !llvm.ptr -> i64
      %254 = llvm.load %236 : !llvm.ptr -> i64
      %255 = llvm.load %240 : !llvm.ptr -> i64
      %256 = arith.muli %252, %255 : i64
      %257 = arith.subi %254, %256 : i64
      llvm.store %257, %240 : i64, !llvm.ptr
      llvm.store %253, %236 : i64, !llvm.ptr
      %258 = llvm.load %245 : !llvm.ptr -> i64
      %259 = llvm.load %242 : !llvm.ptr -> i64
      %260 = llvm.load %245 : !llvm.ptr -> i64
      %261 = arith.muli %252, %260 : i64
      %262 = arith.subi %259, %261 : i64
      llvm.store %262, %245 : i64, !llvm.ptr
      llvm.store %258, %242 : i64, !llvm.ptr
      cf.br ^bb78
    ^bb80:
    %263 = llvm.load %242 : !llvm.ptr -> i64
    %264 = arith.constant 1 : i32
    %266 = arith.extsi %264 : i32 to i64
    %265 = arith.cmpi ne, %263, %266 : i64
    cf.cond_br %265, ^bb81, ^bb82
    ^bb81:
      %267 = arith.constant 0 : i32
      %268 = arith.extsi %267 : i32 to i64
      func.return %268 : i64
    ^bb82:
      cf.br ^bb83
    ^bb83:
    %269 = llvm.load %236 : !llvm.ptr -> i64
    %270 = arith.constant 0 : i32
    %272 = arith.extsi %270 : i32 to i64
    %271 = arith.cmpi slt, %269, %272 : i64
    cf.cond_br %271, ^bb84, ^bb85
    ^bb84:
      %273 = llvm.load %236 : !llvm.ptr -> i64
      %274 = arith.addi %273, %arg1 : i64
      llvm.store %274, %236 : i64, !llvm.ptr
      cf.br ^bb86
    ^bb85:
      cf.br ^bb86
    ^bb86:
    %275 = llvm.load %236 : !llvm.ptr -> i64
    func.return %275 : i64
  }
  func.func @main() -> i32 {
    %277 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
    %278 = llvm.load %277 : !llvm.ptr -> i64
    %279 = arith.constant 1 : i32
    %281 = arith.extsi %279 : i32 to i64
    %280 = arith.addi %278, %281 : i64
    %282 = arith.constant 1 : i32
    %283 = arith.extsi %282 : i32 to i64
    %276 = func.call @calloc(%280, %283) : (i64, i64) -> !llvm.ptr
    %285 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
    %286 = llvm.load %285 : !llvm.ptr -> i64
    %287 = arith.constant 1 : i32
    %289 = arith.extsi %287 : i32 to i64
    %288 = arith.addi %286, %289 : i64
    %290 = arith.constant 1 : i32
    %291 = arith.extsi %290 : i32 to i64
    %284 = func.call @calloc(%288, %291) : (i64, i64) -> !llvm.ptr
    %293 = arith.constant 10000 : i32
    %294 = arith.constant 8 : i32
    %295 = arith.extsi %293 : i32 to i64
    %296 = arith.extsi %294 : i32 to i64
    %292 = func.call @calloc(%295, %296) : (i64, i64) -> !llvm.ptr
    %297 = llvm.mlir.zero : !llvm.ptr
    %298 = llvm.icmp "eq" %276, %297 : !llvm.ptr
    %299 = scf.if %298 -> (i1) {
      %300 = arith.constant true
      scf.yield %300 : i1
    } else {
      %301 = llvm.mlir.zero : !llvm.ptr
      %302 = llvm.icmp "eq" %284, %301 : !llvm.ptr
      scf.yield %302 : i1
    }
    %303 = scf.if %299 -> (i1) {
      %304 = arith.constant true
      scf.yield %304 : i1
    } else {
      %305 = llvm.mlir.zero : !llvm.ptr
      %306 = llvm.icmp "eq" %292, %305 : !llvm.ptr
      scf.yield %306 : i1
    }
    cf.cond_br %303, ^bb87, ^bb88
    ^bb87:
      %307 = arith.constant 1 : i32
      func.return %307 : i32
    ^bb88:
      cf.br ^bb89
    ^bb89:
    %308 = arith.constant 1 : i32
    %309 = arith.constant 0 : i32
    %310 = arith.trunci %308 : i32 to i8
    %311 = arith.extsi %309 : i32 to i64
    %312 = llvm.getelementptr %276[%311] : (!llvm.ptr, i64) -> !llvm.ptr, i8
    llvm.store %310, %312 : i8, !llvm.ptr
    %313 = arith.constant 0 : i32
    %314 = arith.extsi %313 : i32 to i64
    %315 = llvm.mlir.constant(1 : i64) : i64
    %316 = llvm.alloca %315 x i64 : (i64) -> !llvm.ptr
    llvm.store %314, %316 : i64, !llvm.ptr
    %317 = arith.constant 2 : i32
    %318 = arith.extsi %317 : i32 to i64
    %319 = llvm.mlir.constant(1 : i64) : i64
    %320 = llvm.alloca %319 x i64 : (i64) -> !llvm.ptr
    llvm.store %318, %320 : i64, !llvm.ptr
    cf.br ^bb90
    ^bb90:
    %321 = llvm.load %320 : !llvm.ptr -> i64
    %322 = arith.constant 10000 : i32
    %324 = arith.extsi %322 : i32 to i64
    %323 = arith.cmpi sle, %321, %324 : i64
    cf.cond_br %323, ^bb91, ^bb92
    ^bb91:
      %326 = llvm.load %320 : !llvm.ptr -> i64
      %325 = func.call @is_prime_small(%326) : (i64) -> i32
      %327 = arith.constant 1 : i32
      %328 = arith.cmpi eq, %325, %327 : i32
      cf.cond_br %328, ^bb93, ^bb94
      ^bb93:
        %329 = llvm.load %320 : !llvm.ptr -> i64
        %330 = llvm.load %316 : !llvm.ptr -> i64
        %331 = llvm.getelementptr %292[%330] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %329, %331 : i64, !llvm.ptr
        %332 = llvm.load %316 : !llvm.ptr -> i64
        %333 = arith.constant 1 : i32
        %335 = arith.extsi %333 : i32 to i64
        %334 = arith.addi %332, %335 : i64
        llvm.store %334, %316 : i64, !llvm.ptr
        cf.br ^bb95
      ^bb94:
        cf.br ^bb95
      ^bb95:
      %336 = llvm.load %320 : !llvm.ptr -> i64
      %337 = arith.constant 1 : i32
      %339 = arith.extsi %337 : i32 to i64
      %338 = arith.addi %336, %339 : i64
      llvm.store %338, %320 : i64, !llvm.ptr
      cf.br ^bb90
    ^bb92:
    %341 = arith.constant 32 : i32
    %342 = arith.constant 8 : i32
    %343 = arith.extsi %341 : i32 to i64
    %344 = arith.extsi %342 : i32 to i64
    %340 = func.call @calloc(%343, %344) : (i64, i64) -> !llvm.ptr
    %345 = arith.constant 0 : i32
    %346 = arith.extsi %345 : i32 to i64
    %347 = llvm.mlir.constant(1 : i64) : i64
    %348 = llvm.alloca %347 x i64 : (i64) -> !llvm.ptr
    llvm.store %346, %348 : i64, !llvm.ptr
    %349 = arith.constant 1 : i32
    %350 = arith.extsi %349 : i32 to i64
    %351 = llvm.mlir.constant(1 : i64) : i64
    %352 = llvm.alloca %351 x i64 : (i64) -> !llvm.ptr
    llvm.store %350, %352 : i64, !llvm.ptr
    cf.br ^bb96
    ^bb96:
    %353 = llvm.load %352 : !llvm.ptr -> i64
    %354 = llvm.load %352 : !llvm.ptr -> i64
    %355 = arith.muli %353, %354 : i64
    %356 = llvm.mlir.addressof @L : !llvm.ptr
    %357 = llvm.load %356 : !llvm.ptr -> i64
    %358 = arith.cmpi sle, %355, %357 : i64
    cf.cond_br %358, ^bb97, ^bb98
    ^bb97:
      %359 = llvm.mlir.addressof @L : !llvm.ptr
      %360 = llvm.load %359 : !llvm.ptr -> i64
      %361 = llvm.load %352 : !llvm.ptr -> i64
      %362 = arith.remsi %360, %361 : i64
      %363 = arith.constant 0 : i32
      %365 = arith.extsi %363 : i32 to i64
      %364 = arith.cmpi eq, %362, %365 : i64
      cf.cond_br %364, ^bb99, ^bb100
      ^bb99:
        %366 = llvm.load %352 : !llvm.ptr -> i64
        %367 = llvm.load %348 : !llvm.ptr -> i64
        %368 = llvm.getelementptr %340[%367] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %366, %368 : i64, !llvm.ptr
        %369 = llvm.load %348 : !llvm.ptr -> i64
        %370 = arith.constant 1 : i32
        %372 = arith.extsi %370 : i32 to i64
        %371 = arith.addi %369, %372 : i64
        llvm.store %371, %348 : i64, !llvm.ptr
        %373 = llvm.load %352 : !llvm.ptr -> i64
        %374 = llvm.load %352 : !llvm.ptr -> i64
        %375 = arith.muli %373, %374 : i64
        %376 = llvm.mlir.addressof @L : !llvm.ptr
        %377 = llvm.load %376 : !llvm.ptr -> i64
        %378 = arith.cmpi ne, %375, %377 : i64
        cf.cond_br %378, ^bb102, ^bb103
        ^bb102:
          %379 = llvm.mlir.addressof @L : !llvm.ptr
          %380 = llvm.load %379 : !llvm.ptr -> i64
          %381 = llvm.load %352 : !llvm.ptr -> i64
          %382 = arith.divsi %380, %381 : i64
          %383 = llvm.load %348 : !llvm.ptr -> i64
          %384 = llvm.getelementptr %340[%383] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          llvm.store %382, %384 : i64, !llvm.ptr
          %385 = llvm.load %348 : !llvm.ptr -> i64
          %386 = arith.constant 1 : i32
          %388 = arith.extsi %386 : i32 to i64
          %387 = arith.addi %385, %388 : i64
          llvm.store %387, %348 : i64, !llvm.ptr
          cf.br ^bb104
        ^bb103:
          cf.br ^bb104
        ^bb104:
        cf.br ^bb101
      ^bb100:
        cf.br ^bb101
      ^bb101:
      %389 = llvm.load %352 : !llvm.ptr -> i64
      %390 = arith.constant 1 : i32
      %392 = arith.extsi %390 : i32 to i64
      %391 = arith.addi %389, %392 : i64
      llvm.store %391, %352 : i64, !llvm.ptr
      cf.br ^bb96
    ^bb98:
    %393 = arith.constant 0 : i32
    %394 = arith.extsi %393 : i32 to i64
    %395 = llvm.mlir.constant(1 : i64) : i64
    %396 = llvm.alloca %395 x i64 : (i64) -> !llvm.ptr
    llvm.store %394, %396 : i64, !llvm.ptr
    cf.br ^bb105
    ^bb105:
    %397 = llvm.load %396 : !llvm.ptr -> i64
    %398 = llvm.load %348 : !llvm.ptr -> i64
    %399 = arith.cmpi slt, %397, %398 : i64
    cf.cond_br %399, ^bb106, ^bb107
    ^bb106:
      %401 = llvm.load %396 : !llvm.ptr -> i64
      %402 = llvm.getelementptr %340[%401] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %400 = llvm.load %402 : !llvm.ptr -> i64
      %403 = llvm.mlir.addressof @L : !llvm.ptr
      %404 = llvm.load %403 : !llvm.ptr -> i64
      %405 = arith.divsi %404, %400 : i64
      %406 = arith.constant 0 : i32
      %407 = arith.extsi %406 : i32 to i64
      %408 = llvm.mlir.constant(1 : i64) : i64
      %409 = llvm.alloca %408 x i64 : (i64) -> !llvm.ptr
      llvm.store %407, %409 : i64, !llvm.ptr
      cf.br ^bb108
      ^bb108:
      %410 = llvm.load %409 : !llvm.ptr -> i64
      %411 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
      %412 = llvm.load %411 : !llvm.ptr -> i64
      %413 = arith.cmpi sle, %410, %412 : i64
      cf.cond_br %413, ^bb109, ^bb110
      ^bb109:
        %414 = arith.constant 1 : i32
        %415 = llvm.load %409 : !llvm.ptr -> i64
        %416 = arith.trunci %414 : i32 to i8
        %417 = llvm.getelementptr %284[%415] : (!llvm.ptr, i64) -> !llvm.ptr, i8
        llvm.store %416, %417 : i8, !llvm.ptr
        %418 = llvm.load %409 : !llvm.ptr -> i64
        %419 = arith.constant 1 : i32
        %421 = arith.extsi %419 : i32 to i64
        %420 = arith.addi %418, %421 : i64
        llvm.store %420, %409 : i64, !llvm.ptr
        cf.br ^bb108
      ^bb110:
      %422 = arith.constant 0 : i32
      %423 = arith.constant 0 : i32
      %424 = arith.trunci %422 : i32 to i8
      %425 = arith.extsi %423 : i32 to i64
      %426 = llvm.getelementptr %284[%425] : (!llvm.ptr, i64) -> !llvm.ptr, i8
      llvm.store %424, %426 : i8, !llvm.ptr
      %427 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
      %428 = llvm.load %427 : !llvm.ptr -> i64
      %429 = arith.muli %400, %428 : i64
      %430 = arith.constant 1 : i32
      %432 = arith.extsi %430 : i32 to i64
      %431 = arith.addi %429, %432 : i64
      %433 = func.call @isqrt(%431) : (i64) -> i64
      %434 = arith.constant 0 : i32
      %435 = arith.extsi %434 : i32 to i64
      %436 = llvm.mlir.constant(1 : i64) : i64
      %437 = llvm.alloca %436 x i64 : (i64) -> !llvm.ptr
      llvm.store %435, %437 : i64, !llvm.ptr
      cf.br ^bb111
      ^bb111:
      %438 = llvm.load %437 : !llvm.ptr -> i64
      %439 = llvm.load %316 : !llvm.ptr -> i64
      %440 = arith.cmpi slt, %438, %439 : i64
      cf.cond_br %440, ^bb112, ^bb113
      ^bb112:
        %442 = llvm.load %437 : !llvm.ptr -> i64
        %443 = llvm.getelementptr %292[%442] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %441 = llvm.load %443 : !llvm.ptr -> i64
        %444 = arith.cmpi sgt, %441, %433 : i64
        cf.cond_br %444, ^bb114, ^bb115
        ^bb114:
          cf.br ^bb113
        ^bb115:
          cf.br ^bb116
        ^bb116:
        %445 = arith.remsi %400, %441 : i64
        %446 = arith.constant 0 : i32
        %448 = arith.extsi %446 : i32 to i64
        %447 = arith.cmpi eq, %445, %448 : i64
        cf.cond_br %447, ^bb117, ^bb118
        ^bb117:
          %449 = llvm.load %437 : !llvm.ptr -> i64
          %450 = arith.constant 1 : i32
          %452 = arith.extsi %450 : i32 to i64
          %451 = arith.addi %449, %452 : i64
          llvm.store %451, %437 : i64, !llvm.ptr
          cf.br ^bb111
        ^bb118:
          cf.br ^bb119
        ^bb119:
        %453 = func.call @inv_mod(%400, %441) : (i64, i64) -> i64
        %454 = arith.subi %441, %453 : i64
        %455 = arith.remsi %454, %441 : i64
        %456 = llvm.mlir.constant(1 : i64) : i64
        %457 = llvm.alloca %456 x i64 : (i64) -> !llvm.ptr
        llvm.store %455, %457 : i64, !llvm.ptr
        %458 = llvm.load %457 : !llvm.ptr -> i64
        %459 = arith.constant 0 : i32
        %461 = arith.extsi %459 : i32 to i64
        %460 = arith.cmpi eq, %458, %461 : i64
        cf.cond_br %460, ^bb120, ^bb121
        ^bb120:
          llvm.store %441, %457 : i64, !llvm.ptr
          cf.br ^bb122
        ^bb121:
          cf.br ^bb122
        ^bb122:
        %462 = llvm.load %457 : !llvm.ptr -> i64
        %463 = arith.muli %400, %462 : i64
        %464 = arith.constant 1 : i32
        %466 = arith.extsi %464 : i32 to i64
        %465 = arith.addi %463, %466 : i64
        %467 = arith.cmpi eq, %465, %441 : i64
        cf.cond_br %467, ^bb123, ^bb124
        ^bb123:
          %468 = llvm.load %457 : !llvm.ptr -> i64
          %469 = arith.addi %468, %441 : i64
          llvm.store %469, %457 : i64, !llvm.ptr
          cf.br ^bb125
        ^bb124:
          cf.br ^bb125
        ^bb125:
        %470 = llvm.load %457 : !llvm.ptr -> i64
        %471 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
        %472 = llvm.load %471 : !llvm.ptr -> i64
        %473 = arith.cmpi sle, %470, %472 : i64
        cf.cond_br %473, ^bb126, ^bb127
        ^bb126:
          %474 = llvm.load %457 : !llvm.ptr -> i64
          %475 = llvm.mlir.constant(1 : i64) : i64
          %476 = llvm.alloca %475 x i64 : (i64) -> !llvm.ptr
          llvm.store %474, %476 : i64, !llvm.ptr
          cf.br ^bb129
          ^bb129:
          %477 = llvm.load %476 : !llvm.ptr -> i64
          %478 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
          %479 = llvm.load %478 : !llvm.ptr -> i64
          %480 = arith.cmpi sle, %477, %479 : i64
          cf.cond_br %480, ^bb130, ^bb131
          ^bb130:
            %481 = arith.constant 0 : i32
            %482 = llvm.load %476 : !llvm.ptr -> i64
            %483 = arith.trunci %481 : i32 to i8
            %484 = llvm.getelementptr %284[%482] : (!llvm.ptr, i64) -> !llvm.ptr, i8
            llvm.store %483, %484 : i8, !llvm.ptr
            %485 = llvm.load %476 : !llvm.ptr -> i64
            %486 = arith.addi %485, %441 : i64
            llvm.store %486, %476 : i64, !llvm.ptr
            cf.br ^bb129
          ^bb131:
          cf.br ^bb128
        ^bb127:
          cf.br ^bb128
        ^bb128:
        %487 = llvm.load %437 : !llvm.ptr -> i64
        %488 = arith.constant 1 : i32
        %490 = arith.extsi %488 : i32 to i64
        %489 = arith.addi %487, %490 : i64
        llvm.store %489, %437 : i64, !llvm.ptr
        cf.br ^bb111
      ^bb113:
      %491 = arith.constant 1 : i32
      %492 = arith.extsi %491 : i32 to i64
      llvm.store %492, %409 : i64, !llvm.ptr
      cf.br ^bb132
      ^bb132:
      %493 = llvm.load %409 : !llvm.ptr -> i64
      %494 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
      %495 = llvm.load %494 : !llvm.ptr -> i64
      %496 = arith.cmpi sle, %493, %495 : i64
      cf.cond_br %496, ^bb133, ^bb134
      ^bb133:
        %498 = llvm.load %409 : !llvm.ptr -> i64
        %499 = llvm.getelementptr %284[%498] : (!llvm.ptr, i64) -> !llvm.ptr, i8
        %497 = llvm.load %499 : !llvm.ptr -> i8
        %500 = arith.constant 1 : i32
        %502 = arith.extsi %497 : i8 to i32
        %501 = arith.cmpi eq, %502, %500 : i32
        cf.cond_br %501, ^bb135, ^bb136
        ^bb135:
          %503 = llvm.load %409 : !llvm.ptr -> i64
          %504 = arith.muli %400, %503 : i64
          %505 = arith.constant 1 : i32
          %507 = arith.extsi %505 : i32 to i64
          %506 = arith.addi %504, %507 : i64
          %508 = arith.constant 2 : i32
          %510 = arith.extsi %508 : i32 to i64
          %509 = arith.cmpi ne, %506, %510 : i64
          %511 = scf.if %509 -> (i1) {
            %512 = arith.constant 3 : i32
            %514 = arith.extsi %512 : i32 to i64
            %513 = arith.cmpi ne, %506, %514 : i64
            scf.yield %513 : i1
          } else {
            %515 = arith.constant false
            scf.yield %515 : i1
          }
          %516 = scf.if %511 -> (i1) {
            %517 = arith.constant 5 : i32
            %519 = arith.extsi %517 : i32 to i64
            %518 = arith.cmpi ne, %506, %519 : i64
            scf.yield %518 : i1
          } else {
            %520 = arith.constant false
            scf.yield %520 : i1
          }
          %521 = scf.if %516 -> (i1) {
            %522 = arith.constant 23 : i32
            %524 = arith.extsi %522 : i32 to i64
            %523 = arith.cmpi ne, %506, %524 : i64
            scf.yield %523 : i1
          } else {
            %525 = arith.constant false
            scf.yield %525 : i1
          }
          %526 = scf.if %521 -> (i1) {
            %527 = arith.constant 29 : i32
            %529 = arith.extsi %527 : i32 to i64
            %528 = arith.cmpi ne, %506, %529 : i64
            scf.yield %528 : i1
          } else {
            %530 = arith.constant false
            scf.yield %530 : i1
          }
          cf.cond_br %526, ^bb138, ^bb139
          ^bb138:
            %531 = func.call @is_prime_small(%506) : (i64) -> i32
            %532 = arith.constant 1 : i32
            %533 = arith.cmpi eq, %531, %532 : i32
            cf.cond_br %533, ^bb141, ^bb142
            ^bb141:
              %534 = llvm.load %409 : !llvm.ptr -> i64
              %536 = llvm.load %409 : !llvm.ptr -> i64
              %535 = func.call @gcd(%536, %405) : (i64, i64) -> i64
              %537 = arith.divsi %534, %535 : i64
              %538 = arith.constant 1 : i32
              %540 = arith.extsi %538 : i32 to i64
              %539 = arith.cmpi sgt, %537, %540 : i64
              %541 = scf.if %539 -> (i1) {
                %543 = llvm.getelementptr %276[%537] : (!llvm.ptr, i64) -> !llvm.ptr, i8
                %542 = llvm.load %543 : !llvm.ptr -> i8
                %544 = arith.constant 0 : i32
                %546 = arith.extsi %542 : i8 to i32
                %545 = arith.cmpi eq, %546, %544 : i32
                scf.yield %545 : i1
              } else {
                %547 = arith.constant false
                scf.yield %547 : i1
              }
              cf.cond_br %541, ^bb144, ^bb145
              ^bb144:
                %548 = llvm.mlir.constant(1 : i64) : i64
                %549 = llvm.alloca %548 x i64 : (i64) -> !llvm.ptr
                llvm.store %537, %549 : i64, !llvm.ptr
                cf.br ^bb147
                ^bb147:
                %550 = llvm.load %549 : !llvm.ptr -> i64
                %551 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
                %552 = llvm.load %551 : !llvm.ptr -> i64
                %553 = arith.cmpi sle, %550, %552 : i64
                cf.cond_br %553, ^bb148, ^bb149
                ^bb148:
                  %554 = arith.constant 1 : i32
                  %555 = llvm.load %549 : !llvm.ptr -> i64
                  %556 = arith.trunci %554 : i32 to i8
                  %557 = llvm.getelementptr %276[%555] : (!llvm.ptr, i64) -> !llvm.ptr, i8
                  llvm.store %556, %557 : i8, !llvm.ptr
                  %558 = llvm.load %549 : !llvm.ptr -> i64
                  %559 = arith.addi %558, %537 : i64
                  llvm.store %559, %549 : i64, !llvm.ptr
                  cf.br ^bb147
                ^bb149:
                cf.br ^bb146
              ^bb145:
                cf.br ^bb146
              ^bb146:
              cf.br ^bb143
            ^bb142:
              cf.br ^bb143
            ^bb143:
            cf.br ^bb140
          ^bb139:
            cf.br ^bb140
          ^bb140:
          cf.br ^bb137
        ^bb136:
          cf.br ^bb137
        ^bb137:
        %560 = llvm.load %409 : !llvm.ptr -> i64
        %561 = arith.constant 1 : i32
        %563 = arith.extsi %561 : i32 to i64
        %562 = arith.addi %560, %563 : i64
        llvm.store %562, %409 : i64, !llvm.ptr
        cf.br ^bb132
      ^bb134:
      %564 = llvm.load %396 : !llvm.ptr -> i64
      %565 = arith.constant 1 : i32
      %567 = arith.extsi %565 : i32 to i64
      %566 = arith.addi %564, %567 : i64
      llvm.store %566, %396 : i64, !llvm.ptr
      cf.br ^bb105
    ^bb107:
    %568 = arith.constant 0 : i32
    %569 = arith.extsi %568 : i32 to i64
    %570 = llvm.mlir.constant(1 : i64) : i64
    %571 = llvm.alloca %570 x i64 : (i64) -> !llvm.ptr
    llvm.store %569, %571 : i64, !llvm.ptr
    %572 = arith.constant 0 : i32
    %573 = arith.extsi %572 : i32 to i64
    %574 = llvm.mlir.constant(1 : i64) : i64
    %575 = llvm.alloca %574 x i64 : (i64) -> !llvm.ptr
    llvm.store %573, %575 : i64, !llvm.ptr
    %576 = arith.constant 1 : 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
    cf.br ^bb150
    ^bb150:
    %580 = llvm.load %579 : !llvm.ptr -> i64
    %581 = llvm.mlir.addressof @LIMIT_N : !llvm.ptr
    %582 = llvm.load %581 : !llvm.ptr -> i64
    %583 = arith.cmpi sle, %580, %582 : i64
    cf.cond_br %583, ^bb151, ^bb152
    ^bb151:
      %585 = llvm.load %579 : !llvm.ptr -> i64
      %586 = llvm.getelementptr %276[%585] : (!llvm.ptr, i64) -> !llvm.ptr, i8
      %584 = llvm.load %586 : !llvm.ptr -> i8
      %587 = arith.constant 0 : i32
      %589 = arith.extsi %584 : i8 to i32
      %588 = arith.cmpi eq, %589, %587 : i32
      cf.cond_br %588, ^bb153, ^bb154
      ^bb153:
        %590 = llvm.load %571 : !llvm.ptr -> i64
        %591 = arith.constant 1 : i32
        %593 = arith.extsi %591 : i32 to i64
        %592 = arith.addi %590, %593 : i64
        llvm.store %592, %571 : i64, !llvm.ptr
        %594 = llvm.load %571 : !llvm.ptr -> i64
        %595 = llvm.mlir.addressof @TARGET : !llvm.ptr
        %596 = llvm.load %595 : !llvm.ptr -> i64
        %597 = arith.cmpi eq, %594, %596 : i64
        cf.cond_br %597, ^bb156, ^bb157
        ^bb156:
          %598 = llvm.mlir.addressof @L : !llvm.ptr
          %599 = llvm.load %598 : !llvm.ptr -> i64
          %600 = llvm.load %579 : !llvm.ptr -> i64
          %601 = arith.muli %599, %600 : i64
          llvm.store %601, %575 : i64, !llvm.ptr
          cf.br ^bb152
        ^bb157:
          cf.br ^bb158
        ^bb158:
        cf.br ^bb155
      ^bb154:
        cf.br ^bb155
      ^bb155:
      %602 = llvm.load %579 : !llvm.ptr -> i64
      %603 = arith.constant 1 : i32
      %605 = arith.extsi %603 : i32 to i64
      %604 = arith.addi %602, %605 : i64
      llvm.store %604, %579 : i64, !llvm.ptr
      cf.br ^bb150
    ^bb152:
    %606 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %607 = llvm.load %575 : !llvm.ptr -> i64
    %608 = llvm.call @printf(%606, %607) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    func.call @free(%276) : (!llvm.ptr) -> ()
    func.call @free(%284) : (!llvm.ptr) -> ()
    func.call @free(%292) : (!llvm.ptr) -> ()
    func.call @free(%340) : (!llvm.ptr) -> ()
    %613 = arith.constant 0 : i32
    func.return %613 : i32
  }
}