Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Respected Monks,

This will perhaps go in the history of PerlMonks (and otherwise) as the stupidest prime number detector ever!!, but I am trying to learn how to create modules and needed something to work on. If after checking this script, the Monks here decide that I am too stupid to even attempt to create modules, I can certainly live with it.

So, as shown below, the script detects if the supplied number is a prime or not. If the number is a prime and is 5 or 6 digits, the script becomes somewhat slower. At 7 digit primes, it just starts getting exponentially slower and anything above that, it just hangs.

However, if the number is NOT a prime, and even if it is 20 digits, it shows the output in a flash!!

use strict; use warnings; use 5.10.1; use bignum; use Time::HiRes qw(gettimeofday tv_interval); print "Enter the integer: "; chomp (my $prime_candidate = <STDIN>) ; exit if $prime_candidate <= 0 && say "$prime_candidate is not a prime. +"; my $is_prime = 1; my $start_time = [gettimeofday]; foreach my $each_num (2..$prime_candidate) { if ($prime_candidate % $each_num == 0 && $prime_candidate - $each_ +num != 0 ) { say "$prime_candidate is not a prime"; $is_prime = 0; exit; } } my $elapsed_time = tv_interval($start_time); say "$prime_candidate is a prime " if $is_prime != 0; printf "The [$0] script took %2.2f seconds to finish\n", $elapsed_time +;

Given below are the outputs:

$ perl time_is_prime_v1.pl Enter the integer: 99929 99929 is a prime The [time_is_prime_v1.pl] script took 0.79 seconds to finish $ perl time_is_prime_v1.pl Enter the integer: 999983 999983 is a prime The [time_is_prime_v1.pl] script took 7.69 seconds to finish $ perl time_is_prime_v1.pl Enter the integer: 9999991 9999991 is a prime The [time_is_prime_v1.pl] script took 73.97 seconds to finish $ perl time_is_prime_v1.pl Enter the integer: 1320486952377516576 1320486952377516576 is not a prime

So why have I put up this monstrosity here? I just want to find a way to make it work faster so that I can create a module out of it by doing the required changes, test the output by checking it against the output of Math::Prime::Util and be happy that I've created a module!!. I will not ever dare to put it up on CPAN as I know it's too stupid :D, I just want to play with Perl.

Replies are listed 'Best First'.
Re: Stupidest Prime Number detector ever!!
by pryrt (Monsignor) on Jun 23, 2021 at 19:19 UTC
    The problem you are coming across isn't Perl, it's your algorithm. Learning algorithms is great -- and there have been recent discussions on algorithms for Primes (use Super Search to look for "Prime") -- but is that what you want to spend your time on right now?

    Given your stated goal of learning about Perl and how to make modules, I'd just go down that path with your current algorithm, and just not test or debug it on large prime_candidates to avoid long times.

    If you still want to focus on the algorithm, great; here are a few brief comments on your algorithm:

    • Despite your assertion, it won't find all non-primes in a flash; if a non-prime has a very large number as its lowest prime factor, then it will take a long time to get that far
    • You are testing at least 2x as many divisors as you need to: except for 2, there are no even primes, so don't include those in your loop: foreach my $each_num ( 2, map { 2*$_+1 } 1 .. $prime_candidate/2) -- see perldoc -f map for how map works
    • If you also think about odd multiples of 3, that's still too many; other than 3, there are no odd multiples of 3. This means that other than 2 and 3, all primes are +/-1 from a multiple of six (try proving that to yourself based on what I've said already). foreach my $each_num ( 2, 3, map { (6*$_-1, 6*$_+1) } 1 .. 1+$prime_candidate/6)
    • You are still going much higher than you have to for large numbers. The lowest prime factor of a non-prime will always be less than or equal to the number's square root, so divisor checks shouldn't go beyond that. foreach my $each_num ( 2, 3, map { (6*$_-1, 6*$_+1) } 1 .. 1+sqrt($prime_candidate)/6)
    • Read about the Sieve of Eratosthenes if you want to get deeper into algorithm improvements beyond the 2 and 3 divisors.
    • when your prime candidate gets too big, you won't be able to use default math; use bigint to go beyond that limitation

    (Before posting, I see ++choroba beat me to most of those algorithm points. I said some things differently, so I am still posting this.)

      Thank you for such a detailed post, but, the only way I have used map is to gather the output in another array, for example:  my @array (1..1000);  my @odds = map { $_ % 2 != 0 } @array; .So I am taking a bit of a time getting used to the way you are doing it in the sample code, but that's my bad. Thanks again

      .
        my @odds = map { $_ % 2 != 0 } @array;

        That's not going to do what you think. Consider the following:-

        johngg@abouriou:~$ perl -Mstrict -Mwarnings -E ' say for map { $_ % 2 != 0 } 0 .. 10;' 1 1 1 1 1

        The alternating blanks and ones are registering the FALSE and TRUE results of the expression in the map, which essentially has a one to one relation between input on the right and output on the left. What you should be using instead is grep which filters input, only passing to the left those items for which the expression is TRUE.

        johngg@abouriou:~$ perl -Mstrict -Mwarnings -E ' say for grep { $_ % 2 != 0 } 0 .. 10;' 1 3 5 7 9

        Note also that you could dispense with the != 0 as the expression $_ % 2 will evaluate to either 0 or 1.

        johngg@abouriou:~$ perl -Mstrict -Mwarnings -E ' say for grep { $_ % 2 } 0 .. 10;' 1 3 5 7 9

        I hope this is helpful.

        Cheers,

        JohnGG

Re: Stupidest Prime Number detector ever!!
by choroba (Archbishop) on Jun 23, 2021 at 18:56 UTC
    If a candidate is not a prime, it must have a divisor that's less than the square root of the candidate (proof left as an exercise to the reader).
    for my $each_num (2 .. sqrt $prime_candidate) { if ($prime_candidate % $each_num == 0) { say ...

    For another speed-up, skip all the even numbers but 2.

    map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
Re: Stupidest Prime Number detector ever!!
by AnomalousMonk (Bishop) on Jun 23, 2021 at 20:48 UTC
    ... I am trying to learn how to create modules and needed something to work on. ... create a module out of [this monstrosity] by doing the required changes, test the output by checking it ...

    This seems like a reasonable way to learn about creating modules: start with a lousy algorithm, create a MyModule.pm that exports something like is_prime(), create a MyModule.t for the module to test its correct operation (and which can also test execution time), then start improving the algorithm to exercise the process of developing, improving and maintaining the module.

    Ok, you've got the lousy algorithm. So where's the module and its .t script? That seems to me to be the thing to focus on right now. (There are even some who say that one should write the .t script before writing the module!) Believe me, you'll find plenty of ways to improve and extend things once you've got the algorithm encapsulated in a module along with a .t script for it, i.e., once the interface is defined and testable. Interface definition and creation of a testing environment is the first step. Go for it. But at this stage, why are you worrying about better algorithms?


    Give a man a fish:  <%-{-{-{-<

      Hi Anomalous Monk

      ,

      For a moment I was wondering when and why did I reply to myself, but then I noticed the name!!

      I've written a very basic test and updated the original post with it so that it will be there for all to review. Thank you

        Please consider becoming a registered user. This will allow you to edit/update your posts (but you still won't be able to edit any anonymous post, neither your own nor anyone else's). If you're interested in creating an account on PerlMonks, please see Creating an account on PerlMonks. :)

        If you do edit any of your registered-user posts, please review How do I change/delete my post? first.


        Give a man a fish:  <%-{-{-{-<

Re: Stupidest Prime Number detector ever!!
by eyepopslikeamosquito (Bishop) on Jun 24, 2021 at 05:50 UTC
Re: Stupidest Prime Number detector ever!!
by Discipulus (Abbot) on Jun 24, 2021 at 07:08 UTC
    Hello Anonymous Monk,

    dont feel shy showing stupid code! We all started with orrible code, in a language or in another: someone learn fast, others like me still do dubious things after years, but the humilty to show your own error or simple minded solutions is the base of all learning. Many monks can teach you, or well give you precious suggestions, as you already saw. More: many of them take so much care that are able to remember your name and offer a specially crafted help, tailored on your level! So profit it! Is free as in free beer

    > but I am trying to learn how to create modules and needed something to work on

    I have a lot of sparse module stuff in my bibliotheca and you can find interesting [RFC] Discipulus's step by step tutorial on module creation with tests and git (updated on github).

    Have fun!

    L*

    There are no rules, there are no thumbs..
    Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.
Re: Stupidest Prime Number detector ever!!
by BillKSmith (Monsignor) on Jun 23, 2021 at 22:59 UTC
    Implementing your algorithm as a module for your own use can be very easy. Bundling that module into a package suitable for upload to CPAN can be challenging, especially your first module. There are tools to help you build, document, test, install, and update your module suitable for upload. Upload to CPAN is optional. Building all your modules this way makes them easier to use and to update. Unfortunately this tool set has a rather steep learning curve. The best introduction I have found is in the book "Intermediate Perl".

    Start with the algorithm you already have. Save your updates until you are more comfortable with the build process.

    Bill
Re: Stupidest Prime Number detector ever!!
by Anonymous Monk on Jun 23, 2021 at 19:58 UTC

    @Choroba, Thank you Sir!!

    Yes Pryrt, you are absolutely right.

    I picked perl because I find it easier than Python to work with ( I keep messing the space/tabs) and I want to brush up my Perl Skills...

    Thank you for the pointers..

Re: Stupidest Prime Number detector ever!!
by Anonymous Monk on Jun 23, 2021 at 22:30 UTC

    Per Anomalous Monk (and the original intention of the post) "Ok, you've got the lousy algorithm. So where's the module and its .t script? That seems to me to be the thing to focus on right now."

    So here goes. Here's what I have:

    I changed the directory to prime_scripts cause that's where I have everything related to this stuff

    $ cd prime_scripts/

    The  tree command shows the contents of the directory.

    $  tree
    .
    ├── lib
    │†† └── LousyPrime.pm
    ├── README.md
    └── t
        └── prime_test_1.t
    
    2 directories, 3 files
    

    Here's the output of the very basic test. Note:- The  v flag was purposefully not included in the  prove output below so as to avoid long running output.

    $ prove -l t/prime_test_1.t t/prime_test_1.t .. ok All tests successful. Files=1, Tests=1000, 0 wallclock secs ( 0.06 usr 0.01 sys + 0.14 cu +sr 0.01 csys = 0.22 CPU) Result: PASS $

    Here's the Perl Module created based on the script. The output had to be tweaked to match that of Math::Prime::Util is_prime() function.

    And here is the test script

    use strict; use warnings; use 5.10.1; use Math::Prime::Util qw (is_prime); use Test::More; use FindBin::libs; use LousyPrime qw(is_lousy_prime); for (1..1000) { say is_prime($_), is_lousy_prime($_); is ( is_prime($_) , is_lousy_prime($_), "matches"); } done_testing;

    There's a lot more other ways to test, but this is what I've come up with as of now. If the revered monks here do find anything I can improve in the test code written above, please do let me know.

      The naming convention for SomeModule.pm test code is SomeModule.t. This is not enforced in any way, but it's what everyone expects. | Well, it's what I expected, anyway. See Update Note 1 below.

      Some comments on the is_lousy_prime() function code.

      if ( $prime_candidate <= 0 ) { return 0; exit; }
      The exit; statement in the code above will never be reached. No code in the function will be executed after the return 0; statement executes. There's another example of this unreachable-code syntax in the foreach loop further on in the function.

      exit if $prime_candidate == 1 && return 0;
      This is more involved, but essentially the same thing is happening: the exit built-in function will never be executed.
      • If the $prime_candidate == 1 expression is false, exit will not be executed because the if-condition is not true. (Update: The return 0 expression will not be executed because && short-circuits.)
      • If the $prime_candidate == 1 expression is true, the return 0 expression will be executed and will immediately return from the function; exit will not be executed.

      And one more thing: Please, please choose a reasonable indentation style and stick to it!

      Update:
      Notes:

      1. After reading kcott's reply, I thought to myself "Yeah, I do seem to recall spending many happy hours watching files with exactly that nn_name.t format roll by during countless module installs." WTF?!? I think my confusion stems from my practice of writing test scripts with the naming format I mentioned as part of my personal code development best practices. I then conflated personal and general. Oh, well...


      Give a man a fish:  <%-{-{-{-<

        G'day AnomalousMonk,

        "The naming convention for SomeModule.pm test code is SomeModule.t. This is not enforced in any way, but it's what everyone expects."

        I have never encountered that convention — where have you seen it? I certainly wouldn't expect it; I've mostly seen test files starting with numbers and are all lowercase (e.g. nn-name.t).

        A t/ directory I'd create for an OO module might look something like:

        00-load.t # test 'use' 01-instantiate.t # test 'new()' 02-some_func.t # test 'some_func()' ... # and so on ...

        And, as a real world example, here's part of the output of make test for a $work module I ran in the last hour:

        t/00-load.t ............... ok t/01-instantiate.t ........ ok t/02-overload.t ........... ok t/03-validation.t ......... ok ...

        Just in case I was having a sudden, and unexpected, mental breakdown, I checked a few arbitrary, but well-known, CPAN modules' t/ directories:

        Module Repo t/
        Text::CSV https://github.com/makamaka/Text-CSV/tree/master/t
        JSON https://github.com/makamaka/JSON/tree/master/t
        DBI https://github.com/perl5-dbi/dbi/tree/master/t
        XML::LibXML https://github.com/shlomif/perl-XML-LibXML/tree/master/t

        As you can see, for the most part they all follow the same basic naming convention (i.e. number, name, .t). There are a few exceptions (e.g. pod.t) but there are none that look like your SomeModule.t.

        — Ken

        Damn ..indeed foolish of me to write the return 0 and exit that way .. it's not that I don't know about this but I still wrote it...and thanks for the naming convention and indenting tips...I've bothered you enough for today, but I'll update this tomorrow..

Re: Stupidest Prime Number detector ever!!
by Anonymous Monk on Jun 23, 2021 at 20:01 UTC

    Also, big thanks for being nice!! I thought folks would kill me for something stupid like this!!

      Here you will not be killed, only grilled, and that if and only if you choose to keep being stupid despite of advise ;)

      perl -le'print map{pack c,($-++?1:13)+ord}split//,ESEL'
        Here you will not be killed, only grilled, and that if and only if you choose to keep being stupid despite of advise ;)

        And even reaching the state of being grilled takes a VERY long time. I'm often impressed how much patience some of the monks have with people clearly trying to abuse perlmonks as a code writing service, clearly refusing to learn, and clearly refusing to read and understand any of the answers given that do not contain ready-to-use code.

        Alexander

        --
        Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". ;-)

        I've been enough stupid for a day to grill me a whole horse!! Will be back tomorrow for more!!

Re: Stupidest Prime Number detector ever!!
by Anonymous Monk on Jun 24, 2021 at 15:56 UTC

    Side note: The Acme:: name space on CPAN is devoted to "stupid" modules. You might be amused to see what has actually been published. Your prime-number algorithm is no stupider than, say, Acme-Vuvuzela, which was inspired by the South African World Cup. If you use Acme::Vuvuzela; it forks, and the subprocess prints "BZZzzZZzzZZzzZZzz..." until you kill it.

      Itís for joke modules. Acme::Vuvuzela is funny no matter how stupid or pointless. This ďstupidest primeĒ code isnít funny. Itís just a good exercise for discussing and exploring the problem space.