|
(ichimunki) Re: Prime Number Finder
by ichimunki (Priest) on Feb 07, 2002 at 19:59 UTC
|
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. | [reply]
[d/l]
[select] |
|
|
$o++ if $o % 2 == 0;
My criteria for good software:
- Does it work?
- Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
| [reply]
[d/l] |
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." | [reply] |
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
| [reply]
[d/l] |
|
|
Isn't the math wrong here? I get false primes with this.
| [reply] |
|
|
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++;
}
}
| [reply]
[d/l] |
|
|
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.
| [reply] |
Re: Prime Number Finder
by Cybercosis (Monk) on Feb 07, 2002 at 09:09 UTC
|
| [reply] |
|
|
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
| [reply] |
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 | [reply]
[d/l] |
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. | [reply]
[d/l] |
|
|
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);
| [reply]
[d/l] |
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. | [reply]
[d/l] |
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 | [reply]
[d/l] |
|
|
sub is_prime {
("1" x $_[0]) !~ /^(11+)\1+$/
}
| [reply]
[d/l] |
|
|
| [reply] |
|
|
|
|
|
|
|
|
|
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
| [reply]
[d/l]
[select] |
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) | [reply] |
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 | [reply] |
Re: Prime Number Finder
by jbl_bomin (Sexton) 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. | [reply]
[d/l] |
|
|
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";
| [reply] |
|
|
#!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";
| [reply]
[d/l] |
|
|
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);
| [reply]
[d/l] |
|
|
#!/usr/bin/perl
s;;
;x;
while() { print if (1 x++ $\) !~ m }
{
$|^(..+)\1+$|^$\$}
}
| [reply]
[d/l] |
|
|
| [reply] |
|
|
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;
}
};
| [reply]
[d/l] |
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 | [reply] |
|
|
"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
| [reply]
[d/l] |
|
|
| [reply] |
|
|
|
|
my apologies to Blake, no I didn't 'just think that up', it actually is abigails code with a slight modication.
| [reply] |
|
|
| [reply] |
|
|
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.)
| [reply] |
|
|
|
|