//! returns: 0
//! Sieve of Eratosthenes.
//! Find all primes up to 256 using a boolean array.
//! Verify the count of primes matches the known value (54 primes <= 256).

/// Mark all multiples of p as composite.
fn markMultiples(sieve: &mut [bool], p: u32) {
    let mut i: u32 = p * p;
    while i < sieve.len {
        set sieve[i] = true;
        set i += p;
    }
}

/// Run the sieve algorithm.
fn runSieve(sieve: &mut [bool]) {
    // 0 and 1 are not prime.
    set sieve[0] = true;
    set sieve[1] = true;

    let mut p: u32 = 2;
    while p * p < sieve.len {
        if not sieve[p] {
            markMultiples(sieve, p);
        }
        set p += 1;
    }
}

/// Count the number of primes found.
fn countPrimes(sieve: &[bool]) -> u32 {
    let mut count: u32 = 0;
    for composite in sieve {
        if not composite {
            set count += 1;
        }
    }
    return count;
}

/// Collect primes into a slice, return count.
fn collectPrimes(sieve: &[bool], primes: &mut [u32]) -> u32 {
    let mut count: u32 = 0;
    for composite, idx in sieve {
        if not composite {
            if count < primes.len {
                set primes[count] = idx;
                set count += 1;
            }
        }
    }
    return count;
}

/// Check that specific known primes are marked correctly.
fn verifyKnownPrimes(sieve: &[bool]) -> i32 {
    // Known small primes.
    let primes: [u32; 6] = [2, 3, 5, 7, 11, 13];
    for p in primes {
        if sieve[p] {
            return 1;
        }
    }
    // Known small composites.
    let composites: [u32; 5] = [4, 6, 8, 9, 10];
    for c in composites {
        assert sieve[c];
    }
    // Larger primes.
    if sieve[97] {
        return 12;
    }
    if sieve[251] {
        return 13;
    }
    // Larger composites.
    assert sieve[100];
    assert sieve[250];
    return 0;
}

/// Verify that collected primes are in ascending order and all valid.
unsafe fn verifyCollected(sieve: &[bool]) -> i32 {
    let mut primesBuf: [u32; 64] = [0; 64];
    let count = collectPrimes(sieve, &mut primesBuf[..]);

    assert count == 54;

    // First prime should be 2.
    assert primesBuf[0] == 2;
    // Last prime should be 251.
    assert primesBuf[count - 1] == 251;

    // Verify ascending order.
    let collected: *unsafe [u32] = &primesBuf[0..count];
    let mut prev: ?u32 = nil;
    for p in collected {
        if let prevVal = prev {
            assert prevVal < p;
        }
        set prev = p;
    }
    return 0;
}

@default unsafe fn main() -> i32 {
    let mut sieve: [bool; 256] = [false; 256];
    runSieve(&mut sieve[..]);

    let r1 = verifyKnownPrimes(&sieve[..]);
    if r1 <> 0 {
        return 10 + r1;
    }

    // There are 54 primes <= 255 (2, 3, 5, ..., 251).
    assert countPrimes(&sieve[..]) == 54;

    let r3 = verifyCollected(&sieve[..]);
    if r3 <> 0 {
        return 40 + r3;
    }
    return 0;
}