#!/usr/bin/perl -w
#####
# Finding primes with regex's 
#   from Johnson's "Elements of Programming with Perl", pg 196,
#   attributed to Abigail
#
# At the command prompt, type
#
#   ./regex_primes.pl 40
#
# to find all the primes from 2 to 40.
#
####
use strict;

# Get N from the command line
my $default_N = 500;
my $N = shift @ARGV || $default_N;

# The algorithm works like this:
#  First we make a string of N 1's.
#  For N=15, say that's '111111111111111'.
#  Then we look for a substring starting at the left with at least two 1's,
#  and which is repeated at least twice, filling the string.
#  Since the algorithm is greedy, this first tries to divy it up as
#   '111111111111111'.  ''      fails, second piece doesn't match first
#   '11111111111111' .  '1'     fails, second piece doesn't match first
#   ...
#   '11111' . '11111' . '11111' succeeds, so 15 isn't prime. (=5x3)
#  Note that the first capture can't be just (1+), 
#  since that matches  a single 1 which gives the 15x1 factorization.
#  Note also that we need the /^ $/  to match the whole string.

print "Looking for all primes up to $N...\n";
my @primes;
for (my $number = 2; $number <= $N; $number++){
  my $ones = '1'x$number;
  push @primes, $number if $ones !~ /^(11+)\1+$/;
}
print "...done.  Result is \n@primes\n";

