// verifast_options{disable_overflow_check target:ILP32}
extern void abort(void);
//@ requires true;
//@ ensures true;
void reach_error()
//@ requires false;
//@ ensures true;
{}
/*
 * Recursive implementation of prime number test
 * (Sieve of Eratosthenes)
 * 
 * Author: Jan Leike
 * Date: 2013-07-17
 * 
 */

extern int __VERIFIER_nondet_int(void);
//@ requires true;
//@ ensures true;

// Multiplies two integers n and m
int mult(int n, int m) 
//@ requires true;
//@ ensures ((((2 < result) || (result == 0)) || (m < 2)) || (n < 2));
{    if (m < 0) {
        return mult(n, -m);
    }
    if (m == 0) {
        return 0;
    }
    if (m == 1) {
        return 1;
    }
    return n + mult(n, m - 1);
}

// Is n a multiple of m?
int multiple_of(int n, int m) 
//@ requires true;
//@ ensures ((((((m * 2) < (n + 1)) || (n == m)) || (n == 0)) || ((n + m) < 1)) || (m < 1));
{    if (m < 0) {
        return multiple_of(n, -m);
    }
    if (n < 0) {
        return multiple_of(-n, m); // false
    }
    if (m == 0) {
        return 0; // false
    }
    if (n == 0) {
        return 1; // true
    }
    return multiple_of(n - m, m);
}


int is_prime_(int n, int m);
int is_prime(int n);

// Is n prime?
int is_prime(int n) 
//@ requires true;
//@ ensures ((n < 3) || (result == 0));
{    return is_prime_(n, n - 1);
}


int is_prime_(int n, int m) 
//@ requires true;
//@ ensures true;
{    if (n <= 1) {
        return 0; // false
    }
    if (n == 2) {
        return 1; // true
    }
    if (n > 2) {
        if (m <= 1) {
            return 1; // true
        } else {
            if (multiple_of(n, m) == 0) {
                return 0; // false
            }
            return is_prime_(n, m - 1);
        }
    }
}

int main() 
//@ requires module(Primes__verifast_instrumented, true);
//@ ensures junk();
{
    //@ open_module(); 
    int n = __VERIFIER_nondet_int();
    if (n < 1 || n > 46340) {
        // additional branch to avoid undefined behavior 
        // (because of signed integer overflow)
        return 0;
    }
    int result = is_prime(n);
    int f1 = __VERIFIER_nondet_int();
    if (f1 < 1 || f1 > 46340) {
        // additional branch to avoid undefined behavior 
        // (because of signed integer overflow)
        return 0;
    }
    int f2 = __VERIFIER_nondet_int();
    if (f2 < 1 || f2 > 46340) {
        // additional branch to avoid undefined behavior 
        // (because of signed integer overflow)
        return 0;
    }

    if (result == 1 && mult(f1, f2) == n && f1 > 1 && f2 > 1) {
        ERROR: {reach_error();abort();}
    } else {
        return 0;
    }
 return 0; }