lib/bitvector/examples/primes.pl

   1 #!perl -w
   2
   3 ###############################################################################
   4 ##                                                                           ##
   5 ##    Copyright (c) 1995 - 2004 by Steffen Beyer.                            ##
   6 ##    All rights reserved.                                                   ##
   7 ##                                                                           ##
   8 ##    This program is free software; you can redistribute it                 ##
   9 ##    and/or modify it under the same terms as Perl itself.                  ##
  10 ##                                                                           ##
  11 ###############################################################################
  12
  13 use strict;
  14 use vars qw($limit $set $start $stop $min $max $norm $i $j);
  15
  16 use Bit::Vector;
  17
  18 print "\n***** Calculating Prime Numbers - The Sieve Of Erathostenes *****\n";
  19
  20 $limit = 0;
  21
  22 if (-t STDIN)
  23 {
  24     while ($limit < 16)
  25     {
  26         print "\nPlease enter an upper limit (>15): ";
  27         $limit = <STDIN>;
  28         if ($limit =~ /^\s*(\d+)\s*$/) { $limit = $1; } else { $limit = 0; }
  29     }
  30     print "\n";
  31 }
  32 else
  33 {
  34     $limit = 100;
  35     print "\nRunning in batch mode - using $limit as upper limit.\n\n";
  36 }
  37
  38 $set = Bit::Vector->new($limit+1);
  39
  40 print "Calculating the prime numbers in the range [2..$limit]...\n\n";
  41
  42 $start = time;
  43
  44 $set->Primes();
  45
  46 ## Alternative (slower!):
  47
  48 #$set->Fill();
  49 #$set->Bit_Off(0);
  50 #$set->Bit_Off(1);
  51 #for ( $j = 4; $j <= $limit; $j += 2 ) { $set->Bit_Off($j); }
  52 #for ( $i = 3; ($j = $i * $i) <= $limit; $i += 2 )
  53 #{
  54 #    for ( ; $j <= $limit; $j += $i ) { $set->Bit_Off($j); }
  55 #}
  56
  57 $stop = time;
  58
  59 &print_elapsed_time;
  60
  61 $min = $set->Min();
  62 $max = $set->Max();
  63 $norm = $set->Norm();
  64
  65 print "Found $norm prime numbers in the range [2..$limit]:\n\n";
  66
  67 for ( $i = $min, $j = 0; $i <= $max; $i++ )
  68 {
  69     if ($set->contains($i)) { print "prime number #", ++$j, " = $i\n"; }
  70 }
  71
  72 print "\n";
  73
  74 exit;
  75
  76 sub print_elapsed_time
  77 {
  78     my($flag) = 0;
  79     my($sec,$min,$hour,$year,$yday) = (gmtime($stop - $start))[0,1,2,5,7];
  80     $year -= 70;
  81     print "Elapsed time: ";
  82     if ($year > 0)
  83     {
  84         printf("%d year%s ", $year, ($year!=1)?"s":"");
  85         $flag = 1;
  86     }
  87     if (($yday > 0) || $flag)
  88     {
  89         printf("%d day%s ", $yday, ($yday!=1)?"s":"");
  90         $flag = 1;
  91     }
  92     if (($hour > 0) || $flag)
  93     {
  94         printf("%d hour%s ", $hour, ($hour!=1)?"s":"");
  95         $flag = 1;
  96     }
  97     if (($min > 0) || $flag)
  98     {
  99         printf("%d minute%s ", $min, ($min!=1)?"s":"");
 100     }
 101     printf("%d second%s.\n\n", $sec, ($sec!=1)?"s":"");
 102 }
 103
 104 __END__
 105