Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Prime Number Finder

by munchie (Monk)
on Feb 07, 2002 at 00:05 UTC ( #143755=snippet: print w/ replies, xml ) Need Help??

Description: This short script displays the prime numbers found in a range given by the user.
How it works: The user inputs the range $o to $e. A for command checks every number from $o to $e. For each number that evenly goest into the tested number ( if($i % $j==0) ), the script adds the factor ($j) into an array (@prime) at the $p position. $p starts at zero, and increases by 1 with every factor placed in @prime. If the second position of @prime is equal to the tested number, the tested number is prime.
#! Perl

print "Find primes from: ";
$o = <>;
print "to: ";
$e = <>;

for($i=$o; $i<=$e; $i++){
$p=0;
    for($j=1; $j<=$i; $j++){
        if($i % $j==0){

            $prime_[$p] = "$j";
            $p++;
        }
        if ($prime_[1] == $i){
            print "$i is prime";
            print "\n";
        }
    }

}

Comment on Prime Number Finder
Download Code
Re: Prime Number Finder
by Cybercosis (Monk) on Feb 07, 2002 at 09:09 UTC
    Eep! The brute-force approach! Well, if you must, you might as well cut calculation time somewhat:
    -You only have to check the numbers up to one-half of the number you are testing, because the second half are multiplied by the first half to get the number.
    -Multiples of numbers that you've already checked can be skipped.

    ~Cybercosis

    nemo accipere quod non merere

      You only have to check the numbers up to one-half of the number you are testing...

      s/one-half/square root/;

      After Compline,
      Zaxo

Extension To Very Large Numbers - Re: Prime Number Finder
by metadoktor (Hermit) on Feb 07, 2002 at 10:34 UTC
    While your code is very cool. A more powerful approach would probably be to extract the algorithms in Crandall's factor code which allows you to determine if any given number X is prime. You could call this algorithm in the loop for your specified range to solve the problem more quickly. :)

    Of course, for very large X it will take much much longer to determine if X is prime.

    metadoktor

    "The doktor is in."

(ichimunki) Re: Prime Number Finder
by ichimunki (Priest) on Feb 07, 2002 at 19:59 UTC
    You may as well write
    for($i=$o; $i<=$e; $i++){
    as
    print "2 is prime\n" if $o == 2; $o++ if $o % 2; for my $i ( $i=$o; $i<=$e; $i+=2 ){
    That way you start on an odd number and account for the only even number which is prime. There is no need to check even numbers after 2.
      $o++ if $o % 2 == 0;

      My criteria for good software:
      1. Does it work?
      2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Re: Prime Number Finder
by elusion (Curate) on Feb 07, 2002 at 22:32 UTC
    Here's the code I've used for this in the past. I believe it's fairly efficent. If you're going to use it like in the root node in this thread, it's best to check only odd numbers, as suggested by ichimunki.
    #!usr/bin/perl -w use strict; sub prime { my $number = shift; my $d = 2; my $sqrt = sqrt $number; while(1) { if ($number%$d == 0) { return 0; } if ($d < $sqrt) { $d++; } else { return 1; } } } my $number = $ARGV[0]; print prime($number);

    elusion : http://matt.diephouse.com

      Isn't the math wrong here? I get false primes with this.
        nope! they all look prime to me!
        i like it, i'm gonna use it to explain programming loops to a mathmatician friend. i took the liberty to re-arrange a touch...
        sub isPrime { my $number = shift; my $sqrt = sqrt $number; my $d = 2; while (1) { return 0 if ( $number % $d == 0 ); return 1 if ( $d > $sqrt ); $d++; } }
        In fact, you're right, because numbers which only can be devided in 1, themselves and their square root will be marked as prime in this way. make the < into a <= and it is solved.
Re: Prime Number Finder
by munchie (Monk) on Feb 07, 2002 at 23:48 UTC
    Thanks for the feedback. I'm a newbie, and I just made it how I could understand it. I'm sure that the other ways would work, but again, I'm a newb and I'm not that good yet.

    > munchie, the number munchin newb
    Llama: The other other white meat!
    (you had to be there :-P)

Re: Prime Number Finder
by NAstyed (Chaplain) on Feb 08, 2002 at 01:06 UTC
    Well for the first time i can post some real code from my own, i hope that everything goes well.
    This is my solution for the Prime number finder, i now that it has the bug some people says about calculating only with the half or less of the number. (i hope you understand my english to!)

    #! perl use strict; my @list = 1..100; foreach $a (@list){ my@total=(); foreach $b(@list){ if ((int($a/$b)==($a/$b))){ push @total, $b; } } print "$a is prime\n" if ($#total == 1) ; }
    Zonaunderground.com is my Latinamerican underground music site, check it out!</font
Re: Prime Number Finder
by Anonymous Monk on Feb 20, 2002 at 13:03 UTC
    Just a thought, but if you were to increment the first for loop by 2, (primes can't be even with the exception of 0 and 2) you only have to calculate half the iterations, making it twice as fast
Re: Prime Number Finder
by The_Rev (Acolyte) on Feb 20, 2002 at 14:13 UTC
    I had made the post above ragrading half the iterations, but I just thought of a better way to calculate primes. Its not as fast, but its a one liner: while($num <= $max) { push @dynamic, $num if (1 x $num) !~ /^(11+)\1+$/; $num ++; } I hope you find this helpful
      "but I just thought of a better way to calculate primes"
      Did you actually "just think that up" cause it looks quite a bit like one that abigail wrote:
      perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number +]

      -Blake

        my apologies to Blake, no I didn't 'just think that up', it actually is abigails code with a slight modication.

        Reason: (elusion) dupe

        For more information on this node visit: this


        Reason: (elusion) also a dupe (I guess that makes it a triplicate)

        For more information on this node visit: this

        How does this work?
      1 is not prime
        Whether or not 1 is prime is a question of definitions.

        While I admit that it makes more sense to me to say that 1 is not a prime, there is certainly not universal agreement on it. In particular (as I discovered when I took some advanced number theory courses) a number of the people who undertook to compute long lists of primes started their lists with 1. After a while you learn not to be too dogmatic about it. (Though I have to say that there is far more agreement that 1 is not prime than there is on, say, whether 0 is a natural number.)

Re: Prime Number Finder
by eisenstein (Acolyte) on Apr 04, 2002 at 07:45 UTC
    I offer the following as a balance of speed, elegance, and brevity, or at the very least, a demonstration of TMTOWTDI. The algorithm is: take the first number off the top of the list, call it a prime, filter the rest of the list for multiples, repeat.
    use strict; sub primes { my @n = (2..shift); my @p; while (@n && (push @p, shift @n)) { @n = grep { $_ % $p[-1] } @n; } return @p } # find all primes through 100 print join ',',primes(100);
    Note: the grep is fairly costly. Find a better algorithm if you're looking for all primes up to, say, 100,000.
      eisenstein's code is genius, to say the least. I found a different way of the sieve method, and am wondering which is more efficient. Thanks!
      ! usr/bin/perl -w use strict; sub prime{ my (@primes,%n); my $n=shift; foreach my $r(2..$n){ $n{$r}=1; } foreach my $x(2..int(sqrt($n))){ if($n{$x}){ my $a=2*$x; while ($a <= $n){ $n{$a}=undef; $a=$a+$x; } } } foreach my $x(2..$n){ if($n{$x}){ push( @primes, $x); } } return @primes; } #find to 100 print join ',',prime(100);
Re: Prime Number Finder
by tall_man (Parson) on Mar 07, 2005 at 23:00 UTC
    There's also Math::Pari which can do this sort of calculation extremely fast and with huge numbers:
    use strict; use Math::Pari qw(:int PARI nextprime); print "Find primes from: "; chomp(my $o = <>); print "to: "; chomp(my $e = <>); $o = PARI $o; $e = PARI $e; if ($o > $e) { ($o,$e) = ($e,$o); } my $p = nextprime($o); while ($p <= $e) { print "$p is prime\n"; $p = nextprime($p + 1); }

    Update: Fixed the code so that numbers not representable as integers can be converted to PARI objects.

Re: Prime Number Finder
by gu (Beadle) on Nov 11, 2005 at 12:47 UTC
    There's an interesting algorithm for finding whether a number is prime in the documentation of Quantum::Superpositions, which provides quantum-like superpositions in Perl :
    use Quantum::Superpositions ; sub is_prime { my ($n) = @_; return $n % all(2..sqrt($n)+1) != 0 }
    See the documentation for details on how quantum-like superpositions work.

    Gu

    Update : Removed assertion on the complexity of this algorithm
      Nice succinct algorithm, but I must take issue with
      There's an interesting O(1) algorithm
      You do have to execute the algorithm on a classical computer, so Q::S or not, it's most definitely not O(1). It'll be exponential (in the number of bits in $n) because behind the scenes, Q::S is dividing $n by all possible factors (what else could it be doing?). But even on a quantum computer, you still need either a division or gcd circuit (and probably a lot of other stuff), which will take some polynomial time in the number of bits.

      Just because it's a one-liner doesn't make it O(1). Anyway, my favorite cutesy inefficient primality checker is

      sub is_prime { ("1" x $_[0]) !~ /^(11+)\1+$/ }

      blokhead

        some polynomial time in the number of bits.
        If the number of bits is constant, then any polynomial time based on it is constant.

        Caution: Contents may have been coded under pressure.

      Even if you had a quantum computer to run it on, I'm not convinced you'd have an O(1) algorithm unless you also have O(1) algorithms for computing sqrt($n) and 2..$n.

      In any case however the algorithm will give the wrong answer for 2. You can fix that by replacing sqrt($n)+1 with sqrt($n+1).

      Hugo

Re: Prime Number Finder
by jbl_bomin (Acolyte) on Oct 10, 2011 at 19:26 UTC
    Old discussion, but I figure I'll throw in my attempt at calculating primes without modules, and using only recursive functions (no loops)
    #!/usr/bin/env perl use strict; use warnings; use 5.010; $DB::deep = 500; $DB::deep = $DB::deep; # Avoids silly 'used only once' warning no warnings "recursion"; # Identify primes between ARG0 and ARG1 my ($x, $y, $re_int, $result); my ($prime, $is_int); $x = $ARGV[0]; $y = $ARGV[1]; $is_int = sub { my $re_int = qr(^-?\d+\z); my ($x) = @_; $x =~ $re_int ? 1 : 0; }; $prime = sub { my ( $x, $y ) = @_; if ( $y > 1 ) { given ($x) { when ( $is_int->( $x / $y ) ) { return 0; } default { return $prime->( $x, $y - 1 ); } } } else { return 1; } }; $result = sub { my ( $x, $y ) = @_; if ( $x <= $y ) { if ( $prime->($x, $x-1) ) { say $x; } $result->( ( $x + 1 ), $y ); } }; $result->($x, $y);
    Originally posted the above to my blog.
      this is the actual code that works on windows and generates prime numbers upto the number you wish, check below code: #!usr/bin/perl -w use strict; use warnings; my $o = 2; print "enter upto what no.you wish generate the primes: "; my $e = <STDIN>; my ($i,$j,$p); my @prime_=(); print "prime numbers are:\n"; for($i=$o; $i<=$e; $i++){ $p=0; for($j=1; $j<=$i; $j++){ if($i % $j== 0){ $prime_$p = "$j"; $p++; } if ($prime_1 == $i) { print "$i\t"; } } } print"\n";

        this is the actual code which works for windows

        #!usr/bin/perl -w use strict; use warnings; my $o = 2; print "enter upto what number you wish to generate the primes: "; my $e = <STDIN>; my ($i,$j,$p); my @prime_=(); print "prime numbers are:\n"; for($i=$o; $i<=$e; $i++) { $p=0; for($j=1; $j<=$i; $j++) { if($i % $j== 0) { $prime_[$p] = "$j"; $p++; } if ($prime_[1] == $i) { print "$i\t"; } } } print"\n";
Re: Prime Number Finder
by Anonymous Monk on Nov 01, 2013 at 14:25 UTC
    Straight from 'perlthrtut' of 5.18. Just throw two numbers at it: perl primes.pl 2 100
    #!/usr/bin/perl use strict; use warnings; use threads; use Thread::Queue; sub check_num { my ($upstream, $cur_prime) = @_; my $kid; my $downstream = Thread::Queue->new(); while (my $num = $upstream->dequeue()) { next unless ($num % $cur_prime); if ($kid) { $downstream->enqueue($num); } else { print("Found prime: $num\n"); $kid = threads->create(\&check_num, $downstream, $num); } } if ($kid) { $downstream->enqueue(undef); $kid->join(); } } my $stream = Thread::Queue->new(shift()..shift(), undef); check_num($stream, 2);
      TMTOWTDI :-)
      #!/usr/bin/perl s;; ;x; while() { print if (1 x++ $\) !~ m } { $|^(..+)\1+$|^$\$} }

Back to Snippets Section

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: snippet [id://143755]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (10)
As of 2014-09-16 03:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (155 votes), past polls