Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
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+$|^$\$} }

        Can you please explain you code? I'm a noob, honestly i didn't understand your code but it works fine.

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 pondering the Monastery: (13)
As of 2015-07-02 13:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (38 votes), past polls