Doge log

Abby CTO 雑賀 力王のオフィシャルサイトです

素数を求める

特に難しいことはない。
とりあえずメモリが許すまで。
100万個ぐらいは数えれる。


fn prime(n: uint) {
    let mut prime: ~[uint] = do vec::build_sized(n) |push| {
        let mut i: uint = 0;
        while i < n {
            push(0);
            i += 1;
        }};
    let mut ptr: uint = 0;
    let mut j: uint = 5;

    prime[ptr] = 2;
    ptr += 1;
    prime[ptr] = 3;
    ptr += 1;
    
    loop {
        let mut i: uint = 1;
        let mut flg: bool = false;
        
        while prime[i] * prime[i] <= j  {

            if (j % prime[i] == 0) {
                flg = true;
                break;
            }
            i += 1;
        }
        if !flg {
            prime[ptr] = j;
            ptr += 1;
        }
        if prime[n - 1] > 0 {
            break;
        }
        j += 2;
    }

    for prime.each |e| {
        io::println(fmt!("%u", *e));
    }
}

fn main() {
    let args = os::args();
    let n = int::from_str(args[1]).get() as uint;
    prime(n);
}