 Just another Perl shrine PerlMonks

Prime Number Finder

by munchie (Monk)
 on Feb 07, 2002 at 00:05 UTC 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_ == \$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++){
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?
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; print prime(\$number);
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.

~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

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

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 \$_) !~ /^(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).

Hugo

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; \$y = \$ARGV; \$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_ == \$i) { print "\$i\t"; } } } print"\n";
Re: Prime Number Finder
by Anonymous Monk on Mar 31, 2016 at 17:01 UTC
#!/usr/bin/perl # primenum.pl 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 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.

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

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

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 cooling their heels in the Monastery: (5)
As of 2019-10-17 08:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (42 votes). Check out past polls.

Notices?