package Sieve;
use strict;
use warnings;
use Exporter qw<import>;
our @EXPORT_OK = qw<find_primes>;

sub find_primes {
  my ($limit) = @_;
  return [ ]   if ( $limit == 1 ); # no primes under 2
  return [ 2 ] if ( $limit == 2);

  # initialize our sieve as a hash with a default value of `1`, assuming
  # for now that all numbers within the range are prime
  my %sieve = map { $_ => 1 } ( 2 .. $limit );

  foreach my $candidate ( 2 .. $limit ) {
    my $multiple = $candidate * 2; # start at next multiple
    while ( $multiple <= $limit ) {
      $sieve{ $multiple } = 0;
      $multiple += $candidate;
    }
  }

  # store in array @primes all keys of `%sieve` where $sieve{ $_ } is
  # still equal to 1, indicating that the key is a prime number
  my @primes = sort { $a <=> $b } grep{ $sieve{ $_ } } keys %sieve;

  return \@primes;
}

1;