On Mon, 12 Mar 2001 at 18:24:53, Jarkko laid this on us: > sub findgteprime { # find the smallest prime integer greater than or equal to > use integer; > > # It may be sufficient (and more efficient, IF IT IS CORRECT) to use > # $max = 1 + int sqrt $num and calculate it once only, but is it correct? > > my $num = ceil(shift); > return 2 if $num <= 2; > > $num++ unless $num % 2; > > NUM: > for (;; $num += 2) { > my $max = int sqrt $num; > for ($i = 3; $i <= $max; $i += 2) { > next NUM unless $num % $i; > } > return $num; > } > } A bit off the real topic, for which I apologize, but, according to http://www-groups.dcs.st-andrews.ac.uk/~history/HistTopics/Prime_numbers.html the following is an unsolved problem: 4. Is there always a prime between n ** 2 and (n + 1) ** 2 ? (The fact that there is always a prime between n and 2n was called Bertrand's conjecture and was proved by Chebyshev.) If n in the unsolved problem is int sqrt $num, then the algorithm works iff there *is* a prime between n ** 2 and (n + 1) ** 2, solving the problem. My gambling side would favor the existence of such a prime, but I don't like to gamble with code. findgteprime3 benchmarks as well as the uncertain algorithm (findgteprime1) (at least on my Intel PC and an SGI box), and doesn't rely on the status of unsolved problems. But there isn't a *lot* of difference in the runtime of any of the algorithms. -- jpl ======= use Benchmark; # using POSIX::ceil() would be too heavy, and not all platforms have it. sub ceil { my $num = shift; $num = int($num + 1) unless $num == int $num; return $num; } sub findgteprime1 { # find the smallest prime integer greater than or equal to use integer; # It may be sufficient (and more efficient, IF IT IS CORRECT) to use # $max = 1 + int sqrt $num and calculate it once only, but is it correct? my $num = ceil(shift); return 2 if $num <= 2; $num++ unless $num % 2; my $max = 1 + int sqrt $num; my $i; NUM: for (;; $num += 2) { for ($i = 3; $i <= $max; $i += 2) { next NUM unless $num % $i; } return $num; } } sub findgteprime2 { # find the smallest prime integer greater than or equal to use integer; # It may be sufficient (and more efficient, IF IT IS CORRECT) to use # $max = 1 + int sqrt $num and calculate it once only, but is it correct? my $num = ceil(shift); return 2 if $num <= 2; $num++ unless $num % 2; my $i; NUM: for (;; $num += 2) { my $max = int sqrt $num; for ($i = 3; $i <= $max; $i += 2) { next NUM unless $num % $i; } return $num; } } sub findgteprime3 { # find the smallest prime integer greater than or equal to use integer; my $num = ceil(shift); return 2 if $num <= 2; $num++ unless $num % 2; my $i; my $sqrtnum = int sqrt $num; my $sqrtnumsquared = $sqrtnum * $sqrtnum; NUM: for (;; $num += 2) { if ($sqrtnumsquared < $num) { $sqrtnum++; $sqrtnumsquared = $sqrtnum * $sqrtnum; } for ($i = 3; $i <= $sqrtnum; $i += 2) { next NUM unless $num % $i; } return $num; } } $n = 500000; $t = $i = 0; timethis($n, '$t += findgteprime1($i); $i++'); print("\$t = $t\n"); $t = $i = 0; timethis($n, '$t += findgteprime2($i); $i++'); print("\$t = $t\n"); $t = $i = 0; timethis($n, '$t += findgteprime3($i); $i++'); print("\$t = $t\n"); ============== Intel results: timethis 500000: 565 wallclock secs (258.29 usr + 1.15 sys = 259.44 CPU) @ 1927.23/s (n=500000) $t = 125004425341 timethis 500000: 608 wallclock secs (277.77 usr + 1.38 sys = 279.15 CPU) @ 1791.15/s (n=500000) $t = 125004425341 timethis 500000: 534 wallclock secs (256.53 usr + 0.70 sys = 257.23 CPU) @ 1943.79/s (n=500000) $t = 125004425341 SGI results: timethis 500000: 630 wallclock secs (626.84 usr + 0.40 sys = 627.24 CPU) @ 797.14/s (n=500000) $t = 125004425341 timethis 500000: 629 wallclock secs (627.30 usr + 0.40 sys = 627.70 CPU) @ 796.56/s (n=500000) $t = 125004425341 timethis 500000: 627 wallclock secs (624.89 usr + 0.41 sys = 625.30 CPU) @ 799.62/s (n=500000) $t = 125004425341Thread Next