Skip to content

Instantly share code, notes, and snippets.

@binary132

binary132/primes.pl

Last active December 16, 2015 11:49
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save binary132/5430277 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save binary132/5430277 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. binary132 renamed this gist Apr 22, 2013. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.pl → primes.pl
    View file
    File renamed without changes.
  2. binary132 revised this gist Apr 21, 2013. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.pl
    View file
    Original file line number Diff line number Diff line change
    @@ -26,7 +26,7 @@
    }
    }

    # all_numbers that are not marked with '1' are primes
    # all_numbers that are not marked false are primes

    {
    local $, = ' ';
  3. binary132 revised this gist Apr 21, 2013. 1 changed file with 7 additions and 7 deletions.
    14 changes: 7 additions & 7 deletions gistfile1.pl
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,5 @@
    #!/usr/bin/perl

    # Bodie Solomon 2013

    use Getopt::Std;
    use vars '$opt_p';

    @@ -11,24 +9,26 @@
    getopts('p:');

    # create a list of numbers from 2 to n
    # numbers which are not prime will be "marked" with a 1
    # numbers which are not prime will be "marked" with a 0

    my %all_numbers = map { $_ => 0 } (2 .. $opt_p);
    my %all_numbers = map { $_ => 1 } (2 .. $opt_p);

    # all composite numbers <= $opt_p will have one factor <= sqrt( $opt_p )
    for my $factor (2 .. sqrt( $opt_p )) {
    # mark all values n that are products of $factor, n <= $opt_p
    # so, if value not already marked, make a map of its products
    # up to $factor * int($opt_p/$factor)
    # e.g. 100/9 = 11.111.. -> 9*11 = 99 <= 100 < 108 = 9*12
    unless ($all_numbers{$factor} == 1)
    if($all_numbers{$factor})
    {
    $all_numbers{$_} = 1
    $all_numbers{$_} = 0
    for map { $factor * $_ } ( $factor .. int($opt_p/$factor) );
    }
    }

    # all_numbers that are not marked with '1' are primes

    {
    local $, = ' ';
    print sort { $a <=> $b } grep { ! $all_numbers{$_} } keys %all_numbers;
    print sort { $a <=> $b } grep { $all_numbers{$_} } keys %all_numbers;
    }
  4. binary132 revised this gist Apr 21, 2013. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.pl
    View file
    Original file line number Diff line number Diff line change
    @@ -30,5 +30,5 @@

    {
    local $, = ' ';
    print sort { $a <=> $b } grep { $all_numbers{$_} == 0 } keys %all_numbers;
    print sort { $a <=> $b } grep { ! $all_numbers{$_} } keys %all_numbers;
    }
  5. binary132 revised this gist Apr 21, 2013. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.pl
    View file
    Original file line number Diff line number Diff line change
    @@ -17,7 +17,7 @@

    # all composite numbers <= $opt_p will have one factor <= sqrt( $opt_p )
    for my $factor (2 .. sqrt( $opt_p )) {
    # mark all values n that are products of $factor, n <= $opt_p
    # mark all values n that are products of $factor, n <= $opt_p
    # so, if value not already marked, make a map of its products
    # up to $factor * int($opt_p/$factor)
    # e.g. 100/9 = 11.111.. -> 9*11 = 99 <= 100 < 108 = 9*12
  6. binary132 revised this gist Apr 21, 2013. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.pl
    View file
    Original file line number Diff line number Diff line change
    @@ -10,7 +10,7 @@

    getopts('p:');

    # 1. create a list of numbers from 2 to n
    # create a list of numbers from 2 to n
    # numbers which are not prime will be "marked" with a 1

    my %all_numbers = map { $_ => 0 } (2 .. $opt_p);
  7. binary132 created this gist Apr 21, 2013.
    34 changes: 34 additions & 0 deletions gistfile1.pl
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,34 @@
    #!/usr/bin/perl

    # Bodie Solomon 2013

    use Getopt::Std;
    use vars '$opt_p';

    use strict;
    use warnings;

    getopts('p:');

    # 1. create a list of numbers from 2 to n
    # numbers which are not prime will be "marked" with a 1

    my %all_numbers = map { $_ => 0 } (2 .. $opt_p);

    # all composite numbers <= $opt_p will have one factor <= sqrt( $opt_p )
    for my $factor (2 .. sqrt( $opt_p )) {
    # mark all values n that are products of $factor, n <= $opt_p
    # so, if value not already marked, make a map of its products
    # up to $factor * int($opt_p/$factor)
    # e.g. 100/9 = 11.111.. -> 9*11 = 99 <= 100 < 108 = 9*12
    unless ($all_numbers{$factor} == 1)
    {
    $all_numbers{$_} = 1
    for map { $factor * $_ } ( $factor .. int($opt_p/$factor) );
    }
    }

    {
    local $, = ' ';
    print sort { $a <=> $b } grep { $all_numbers{$_} == 0 } keys %all_numbers;
    }