Re: [MacPerl] Prime Numbers [Was: pi, slightly off topic]

[Ken Williams <ken@forum.swarthmore.edu>]

jwblist@olympus.net (John W Baxter) wrote:
>(Does it do the first 1000 primes *correctly*?  If not, then the time to
>produce the first 1000 primes is infinite, and speeding it up would be done
>first by making it correct.)
>  --John

If you doubt that it works, you can easily modify it to give you the factors of
the composite numbers:

  my ($pidx, $cidx);
  $_ = 1;

  while (++$_) {
    if ( (1 x $_) =~ /^(11+)\1+$/ ) {
      print "$_ is composite (" . length($1) . "*" . $_/length($1) . "). ";
      print " Found " . ++$cidx . " composites\n";
    } else {
      print "$_ is prime; found " . ++$pidx . " primes\n";
    }
  }

As for whether it can be sped up, it seems you can make it a little faster by
using /^(11+?)\1+$/ instead (non-greedy).  I doubt it can be made much faster,
though - it doesn't even use sieve methods to check division, i.e. it would
check a number for divisibility by 6, then 3, then 2.  And it will check 17 for
divisibility by 17, then 16, then 15, etc., when at the very least a smart
person would start with something around 9.

The non-greedy version checks first for divisibility by 2, then 3, etc. in
ascending order instead of descending, and that will always succeed faster if
it's going to succeed.  I think.


  -------------------                            -------------------
  Ken Williams                             Last Bastion of Euclidity
  ken@forum.swarthmore.edu                            The Math Forum



===== Want to unsubscribe from this list?
===== Send mail with body "unsubscribe" to macperl-request@macperl.org