Mercurial > algorithms
changeset 6:9e16e99a4a10
Added sieve of Eratosthenes
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Mon, 04 May 2015 17:23:45 -0500 |
parents | d48b3fb142f0 |
children | e1578d3eee36 |
files | sieve_of_eratosthenes/sieve.pl |
diffstat | 1 files changed, 72 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/sieve_of_eratosthenes/sieve.pl Mon May 04 17:23:45 2015 -0500 1.3 @@ -0,0 +1,72 @@ 1.4 +#!/usr/bin/env perl 1.5 + 1.6 +use strict; 1.7 +use warnings; 1.8 + 1.9 +sub sieve_of_eratosthenes { 1.10 + my $limit = shift; 1.11 + 1.12 + my @nums = []; 1.13 + for ( my $i = 2; $i <= $limit; $i ++ ) { 1.14 + $nums[$i] = 0; 1.15 + } 1.16 + 1.17 + my $factor = 2; 1.18 + my $done = 0; 1.19 + while (not $done) { 1.20 + my $i = $factor; 1.21 + while ( $i <= $limit ) { 1.22 + $i += $factor; 1.23 + $nums[$i] = 1; 1.24 + } 1.25 + 1.26 + my $new_factor = $factor + 1; 1.27 + for ( my $j = $new_factor ; $j <= $limit; $j++ ) { 1.28 + if ( $nums[$new_factor] == 0 ) { 1.29 + last; 1.30 + } 1.31 + } 1.32 + if ( $new_factor > $limit ) { 1.33 + $done = 1; 1.34 + } 1.35 + else { 1.36 + $factor = $new_factor; 1.37 + } 1.38 + } 1.39 + 1.40 + my @primes; 1.41 + for ( my $i = 2; $i <= $limit; $i ++ ) { 1.42 + ( $nums[$i] == 0 ) and push @primes, $i; 1.43 + } 1.44 + return \@primes; 1.45 +} 1.46 + 1.47 +sub sieve2 { 1.48 + my $limit = shift; 1.49 + 1.50 + my @nums = []; 1.51 + for ( my $i = 2; $i <= $limit; $i ++ ) { 1.52 + $nums[$i] = 1; 1.53 + } 1.54 + 1.55 + for ( my $i = 2; $i <= sqrt($limit); $i ++ ) { 1.56 + if ( $nums[$i] ) { 1.57 + for ( my $j = $i * $i ; $j <= $limit; $j += $i ) { 1.58 + $nums[$j] = 0; 1.59 + } 1.60 + } 1.61 + } 1.62 + 1.63 + my @primes; 1.64 + for ( my $i = 2; $i <= $limit; $i ++ ) { 1.65 + ( $nums[$i] ) and push @primes, $i; 1.66 + } 1.67 + return \@primes; 1.68 +} 1.69 + 1.70 +my $primes = sieve2( $ARGV[0] ); 1.71 +#my $primes = sieve_of_eratosthenes( $ARGV[0] ); 1.72 + 1.73 +foreach my $prime (@{$primes}) { 1.74 + print "$prime\n"; 1.75 +}