Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

YAPNC: Yet another prime number checker?

by snafu (Chaplain)
on Oct 08, 2002 at 21:48 UTC ( [id://203769]=perlquestion: print w/replies, xml ) Need Help??

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

I hope this is a good place to put this. I was on www.ca-osi.com doing some geek challenges and started perusing the site for some ideas how to solve one of the puzzles when I happened upon a prime number generator. I wondered about how the developer was doing his generator and the fact that it only went from 1 to 100. I decided to have my own go at it. Well, here it is. If you folks could take a gander at it and tell me what you think I'd appreciate it. If you guys like it I will place it in snippets. I don't want to place something there that is buggy or cludgy which is why I figured placing it here first would be a good idea.

#!/usr/bin/perl -w use strict; use File::Basename; my $plProgName = basename($0); my $plBaseName = fileparse($plProgName,'\.[^\.]*'); my $input = $ARGV[0] || &usage; my $fail = 0; if ( $input =~ /[a-z]/i ) { &usage(2); } print "Big numbers will take a little while...\n\n" if ( $input > 100000 ); for ( 1 .. $input ) { my $up = $_; my $last_digit = substr($up,length($up) - 1,1); my $mod = $input % $up; next if ( $last_digit == 5 or $last_digit = 0 ); if ( $mod == 0 ) { $fail++; # print "\$fail: $fail\n"; unless ( $input == 1 or $input == 2 or $input == 5 ) { if ( $input == $up and $fail == 2 ) { print "$input is a prime\n"; exit(0); } } else { print "$input is a prime\n"; exit(0); } } } print "$input is \c[[1mnot\c[[m prime.\n"; sub usage { my $errcode = shift || 1; print "\nUsage: $plProgName integer\n\n"; exit($errcode); }
Oh, now this isn't a generator. This is a number checker. So just run it with a number to check. I am not doing any bounds checking so if you use a huge number this script will be limited by what your machine arch can handle. I am also not checking for negative numbers so Im not sure how it will work if you use one.

Any and all feedback would be very appreciated.

I made some small changes to the other guy's code (since his was a generator and mine was a checker...I made his a checker and left his algorythm alone) and tried checking how quick his worked compared to mine and mine was significantly faster than his. This is a learning project for me so I am not looking at getting ripped to shreds unless it will be beneficial to me. :) TIA guys.

_ _ _ _ _ _ _ _ _ _
- Jim
Insert clever comment here...

Replies are listed 'Best First'.
Re: YAPNC: Yet another prime number checker?
by Enlil (Parson) on Oct 08, 2002 at 22:26 UTC
    I have a couple of questions regarding what you are doing. On the following line:

    next if ( $last_digit == 5 or $last_digit = 0 );

    did you mean:

    next if ( $last_digit == 5 or $last_digit == 0 );

    also to make it run even faster you might want to look to have it only check from $input to sqrt($input). If it does not fail up to the
    sqrt($input) it will not fail past that point.

    -Enlil

      Whoa! Good catch :) I will fix that. You are right, that is what I intended to do.

      Another thing that has been suggested to me is an xor to ignore certain values passed or some kind of bit-shifting for the same purpose. I need to look into that more since that kind of arithematic manipulation is really new to me.

      _ _ _ _ _ _ _ _ _ _
      - Jim
      Insert clever comment here...

Re: YAPNC: Yet another prime number checker?
by Abigail-II (Bishop) on Oct 09, 2002 at 07:24 UTC
    This is a very inefficient algorithm. What you are doing is counting all the divisors of a number (with the exception of divisors divisible by 5) and call it a prime if there are just 2 divisors (special casing a few numbers).

    It's of course a lot more efficient to decide a number is prime as soon as you have found a divisor > 1 and smaller or equal to sqrt (number). No need to do millions of divisions to decide 100000000 is prime after finding out it's divisible by 2.

    Abigail

      # Yeah, anything less than 2 is prime.... ;-) $ARGV[0] % $_ or die "$ARGV[0] is composite\n" for 2 .. sqrt $ARGV[0]; die "$ARGV[0] is prime\n"
      Abigail
Re: YAPNC: Yet another prime number checker?
by JaWi (Hermit) on Oct 09, 2002 at 06:56 UTC
    First of all: the used algorithm passed '1' for a prime while it isn't! A prime should have two and only two different integer divisors...

    Secondly, you could speed things up a little more: you only need to check all integer numbers up to ceil( $input / 2 ) because of the commutative properties of integers (2*3 == 3*2).
    Furthermore, prime are always (except for '2', so almost always) odd numbers, so you could skip them in your test for even more speed improvement!

    -- JaWi

    "A chicken is an egg's way of producing more eggs."

      You can stop at sqrt($input).

      Example:
      The divisors of 100 are:
      1, 2, 4, 5, 10, 20, 25, 50, 100. They come in pairs as follows:

      1*100 = 100 2*50 = 100 4* 25= 100 5*20 = 100 10*10 =100 20*5= 100
      and so on. So at 10 which is sqrt(10) you are at the point where the second factor is smaller than the first and you have already tested for this pair.

        nefertari++: You're absolutely and totally right! Well, even less cycles to perform :-)

        -- JaWi

        "A chicken is an egg's way of producing more eggs."

      I don't know if you could work this in, might mean even less cycles; discount any number that ends in a 5 or 0 (25, 50, 165) 'cause they're all multiple of 5 (except 5 itself that is) (actually 0 is already covered as its a multiple of 2)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://203769]
Approved by JaWi
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (5)
As of 2024-03-28 14:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found