http://qs321.pair.com?node_id=430254

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

Hello Monks,

If I have a certain number (eg 10) and I want to find out which are the closest prime numbers to it: (5 7 11 13).

Please give me some ideas on how that can be accomplished.

Thank you.

Replies are listed 'Best First'.
Re: a close prime number
by chromatic (Archbishop) on Feb 11, 2005 at 20:48 UTC

    That's really easy:

    sub find_closest_primes { my $number = shift; my @close_primes; for my $close (find_close_numbers( $number )) { push @close_primes, $close if is_prime( $close ); } return @close_primes; }

    All you have to do is fill in the behavior of find_close_numbers() and is_prime()!

      Your solution reminds me of me of a article currently referenced from the Joel on Software homepage, which talks about the the do-magic-here step.

      :)

        I don't necessarily think of it as magic; I didn't know what the supplicant would consider a "close" number nor did I know which prime number finding algorithm he might find acceptable.

        It's not really a joke answer. It's how I would divide the problem if I were doing it.

Re: a close prime number
by dragonchild (Archbishop) on Feb 11, 2005 at 20:41 UTC
    What have you tried? What directions are you thinking of?

    If you don't provide those items, we quite reasonably are going to consider this an attempt to get us to do your homework for you.

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

      I am thinking of using Math::Prime::Simple. The way with that was:

      @ranges = ( [ $myNum-100, $myNum+100 ] ); $primes = prime( @ranges );

      But this gives me ranges from -100 to +100 of $myNum. And I would have to parse through and check to see the 2 primenumbers smaller and greater than $myNum. Is there any nicer way?

      Thanks

        There is no way of predicting what the next prime number is, given any other number. If there was, then current cryptography methods wouldn't work. All prime number generators are, for the most part, variations on brute force. The method you're looking at is probably as good as any.

        Being right, does not endow the right to be rude; politeness costs nothing.
        Being unknowing, is not the same as being stupid.
        Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
        Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

        You can do better than using the arbitrary range of +100/-100, (which isn't going to be good enough when your numbers get larger). Here's a an introductory explaination of prime number distribution you might find helpful.


        -- All code is 100% tested and functional unless otherwise noted.
Re: a close prime number
by Limbic~Region (Chancellor) on Feb 11, 2005 at 22:29 UTC
    Anonymous Monk,
    Ok - this is an adaptation of Challenge: Nearest Palindromic Number. Since the mathematical lesson has already been explained, I decided to spruce up the Perl so that there might be a lesson in it.
    #!/usr/bin/perl use strict; use warnings; my $nearest_prime = nearest(); for ( map { int( rand 9998 ) + 2 } 1 .. 50 ) { print "$_ : ", $nearest_prime->( $_ ), "\n"; } sub nearest { my $prime = is_prime(); return sub { my $n = shift; return $n if $prime->( $n ); my $pos = $n; ++$pos while ! $prime->( $pos ); $pos = $pos - $n; my $neg = $n; --$neg while ! $prime->( $neg ); $neg = $n - $neg; return $pos > $neg ? $n - $neg : $n + $pos; } } sub is_prime { my %prime = map { $_ => 1 } (2, 3, 5, 7); my %not_prime; return sub { my $n = shift; return 1 if $prime{ $n }; return 0 if $n % 2 == 0 || exists $not_prime{ $n }; for ( 3 .. sqrt $n ) { return $not_prime{ $n } = 0 if $n % $_ == 0; } return $prime{ $n } = 1; }; }
    I will leave converting the code from the nearest prime to the nearest N primes as an exercise for the reader.

    Cheers - L~R

      The speed of the is_prime function can be increase by about 140% by using the 2 4 trick used below.
      sub is_prime { my %prime = map { $_ => 1 } (2, 3, 5, 7); my %not_prime; return sub { my $n = shift; return 1 if $prime{ $n }; return 0 if $n % 2 == 0 || $n % 3 == 0 || exists $not_prime{ $n }; my $last = int sqrt $n; for ( my $x = 5; $x <= $last ;) { return $not_prime{ $n } = 0 if $n % $x == 0; $x += 2; return $not_prime{ $n } = 0 if $n % $x == 0; $x += 4; } return $prime{ $n } = 1; }; }
      This version skips all of the numbers that are divisable by 2 and 3. Not checking numbers divisable by 2 is obvious, but not checking numbers divisable by 3 is less so, but reduces the search space by 25%.
        gam3,
        I have added several improvements:
        • Cache is now persistent
        • Primeness is determined in C
        • The 2 4 trick is used in checking near numbers also
        • An iterator is used in lieu of a stack
        I wonder if it's quicker to add the digits of the number when you're checking to see if it's divisible by three and seeing if that resultant sum is divisible by three.
Re: a close prime number
by TedPride (Priest) on Feb 11, 2005 at 22:03 UTC
    use strict; use warnings; print nearPrime(100000); sub nearPrime { my $num = shift; $_ = 0; return $num if isPrime($num); while (1) { $_++; return ($num - $_) if isPrime($num - $_); return ($num + $_) if isPrime($num + $_); } } BEGIN { my @primes = (2); my $max = 2; sub isPrime { my $num = shift; my $root = int sqrt $num; if ($root > $max) { for (($max+1)..$root) { push(@primes, $_) if isPrime($_); } $max = $root; } for (@primes) { return 0 if ($num % $_ == 0); } return 1; } }
      I think yours is working a little harder than necessary. (Update: I didn't recognize the cache.) Also note that you ought to localize $_ if you're going to use it where Perl isn't automatically localizing it.
      for (10,15,20831323,99,100) { print "$_: ", nearPrime($_), "\n"; } sub nearPrime { my $num = shift; local $_ = 0; # otherwise tries to modify for loop var above return $num if isPrime($num); while (1) { $_++; return ($num - $_) if isPrime($num - $_); return ($num + $_) if isPrime($num + $_); } } ...
      An alternative nearPrime sub:
      sub nearPrime { my $num = shift; my $sign = 1; return $num if isPrime($num); for (0..$num) { $num += $sign * $_; return $num if isPrime($num); $sign = -$sign; } }
      And this isPrime does a little less work by checking only odd numbers:
      BEGIN { my @primes = (2, 3); my $max = 3; sub isPrime { my $num = shift; my $root = int sqrt $num; while ($max <= $root) { $max += 2; push(@primes, $max) if isPrime($max); } for (@primes) { last if $_ > $root; return 0 if ($num % $_ == 0); } return 1; } }

      Caution: Contents may have been coded under pressure.
      One other bug:
      for (@primes) { last if $_ > $root; # If you have checked bigger primes, +you don't want to go through all of them! print("$_ divides $num\n"), return 0 if ($num % $_ == 0); }

      Caution: Contents may have been coded under pressure.
Re: a close prime number
by renz (Scribe) on Feb 11, 2005 at 22:45 UTC

    Update: Removed entire program and restructured post around isPrime() -- full code here.

    Update2: For those of you who aren't familiar with the problems of Fermat's Little Theorem check out this.

    This isn't *exactly* what you wanted, but since mr_mischief and I were talking about it yesterday, and a primality question popped up today, I thought I'd post it. If nothing else, you can make use of isPrime()... It could be easily adapted to check a range of numbers for primes, a task in this case left to the reader.

    # thanks to: mr_mischief for help and efficient isPrime() rewrite. sub isPrime { my $num = $_[0]; my $val = 'prime'; if ($num =~ /^\d+$/ && $num >= 2) { my $mod = 2; my $div = int($num / 2); while ($mod <= $div) { ($num % $mod) == 0 ? ($val = 'composite', last) : $mod++; } } else { $val = 'neither'; } print ' ' . $num . ":\t\t$val\n"; } # rz/021005

    A couple of nice things about this isPrime() is that it should not be fooled by pseudoprimes (because we aren't exactly using Fermat's little theorem to test for them) or any data that should not be prime (thanks to /^\d+$/). Without that regex, weird things would happen (well, weird in the context of what we are doing), like returning prime for numbers that are obviously not prime:

    (3.5 % 2) = 1
    (which evaluates to prime -- best to ignore decimals and negatives since they can't be prime anyway.)

    /renz.
    "Are you merely the spirit of these/ Bones that shelter me?"
    --Dax Riggs, Dressed Up In Smoke.