 Problems? Is your data what you think it is? 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 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 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 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;

sub check_num {
my (\$upstream, \$cur_prime) = @_;
my \$kid;

while (my \$num = \$upstream->dequeue()) {
next unless (\$num % \$cur_prime);

if (\$kid) {
\$downstream->enqueue(\$num);
} else {
print("Found prime: \$num\n");
}
}

if (\$kid) {
\$downstream->enqueue(undef);
\$kid->join();
}
}

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;
}
};
A reply falls below the community's threshold of quality. You may see it by logging in.

Create A New User
Domain Nodelet?
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 imbibing at the Monastery: (3)
As of 2021-11-27 15:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?