Code kata: решето Эратосфена

Один из простейших эффективных по процессору тестов на простоту чисел с известным серьёзным недостатком — лимитом сверху. Заняло минут 10.

Возможна ленивая реализация. Сделаю отдельно.

#! /usr/bin/perl
use strict;
use warnings;

use Test::Most;

my $TOP = 100000;
our @sieve = 0 .. $TOP;

undef $sieve[1];
for my $i (2 .. $TOP / 2) {
	if ($sieve[$i]) {
		for (my $weed = $i * 2; $weed <= $TOP; $weed += $i) {
			undef $sieve[$weed];
		}
	}
}

sub is_prime {
	my $num = shift;

	return defined $sieve[$num];
}

ok(!is_prime(1));
ok(is_prime(2));
ok(is_prime(3));
ok(!is_prime(4));
ok(!is_prime(9));
ok(!is_prime(10000));
ok(is_prime(8191));
ok(is_prime(86243));
ok(!is_prime(86241));
ok(!is_prime(86242));

done_testing;