Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer

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++){
    for($j=1; $j<=$i; $j++){
        if($i % $j==0){

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


Replies are listed 'Best First'.
(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++){
    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?
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.


    "The doktor is in."

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 :

      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 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.


    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,

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) ; } is my Latinamerican underground music site, check it out!</font
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($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 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 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.


    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+$/ }


        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).


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 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 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 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.

Re: Prime Number Finder
by Anonymous Monk on Mar 31, 2016 at 17:01 UTC
    #!/usr/bin/perl # use warnings; use strict; use Term::ANSIColor; my ($primer, $entered); my $breakout = 0; print "\nPrime numbers between 2 and your entered number.\n\n"; while ($breakout != 1) { print "\nEnter a number: "; $entered = <STDIN>; chomp $entered; print "\n"; if ($entered <= 2) { print "Your number must be greater than 2, try again.\n"; } else { print color('red'); print "Prime numbers between 2 and $entered are: "; print color('reset'); for (my $x = 3; $x <= $entered; $x++) { my $y = 0; my $z = 0; while ($y <= $x) { $y++; if (($x % $y) == 0) { $z++; } } if ($z < 3) { print "$x "; } } print "\n\n"; $breakout = 1; } };
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 +]


        How does this work?
        my apologies to Blake, no I didn't 'just think that up', it actually is abigails code with a slight modication.
      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.)

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (2)
As of 2016-09-25 05:33 GMT
Find Nodes?
    Voting Booth?
    Extraterrestrials haven't visited the Earth yet because:

    Results (464 votes). Check out past polls.