http://www.perlmonks.org?node_id=610221

in reply to ulam's spiral too slow

Hi orange,

The main problem you're having is in your is_prime subroutine.

You are calculating primes based on whether a number N is divisible by any value from 1 to N, when you only need to be looking at all odd values between 3 and sqrt(N), but including the special case of 2.  Additionally, you should be caching the values (you may have thought you were doing this with my @prime_;, but the correct way would be to use a hash.  (Additionally, though you were checking the value with if (\$prime_[1] == \$num) { \$b = 1; }, you were still letting the entire loop run its course, and thus defeating its purpose).

Update:  But see grinder's important comment, below, on an even further degree of optimization.

Update:  bart caught a bug in my program; namely, that it needs to test for division by 2!  I've added this in the code below.

Here's a rewrite of the entire program:

```#!/usr/local/bin/perl

use strict;
use warnings;

use Tk;

my \$NumOfPrimes = 0;
my (\$colr, \$counter);
my(\$o, \$s) = (250, 20);
my(\$pi, \$x, \$y) = (3.1415926, 0, 0);
print "type the maximum number for the prime spiral \n";
my \$lastnumber = <>;
my \$mw = MainWindow->new;
my \$c = \$mw->Canvas(-width => 500, -height => 500);
\$c->pack;
\$c->createLine(50, 250, 450, 250);
\$c->createText(10, 250, -fill => 'blue', -text => 'X');
\$c->createLine(250, 50, 250, 450);
\$c->createText(250, 10, -fill => 'blue', -text => 'Y');

my \$num      = 0;
my \$order    = 0;
my \$pnts     = 0;
my \$pntcycle = 0;
OUTER:
for (my \$i= 1; \$i <= 250; \$i += 1) {
\$order=\$order+1;
if (\$order == 5) {\$order = 1;}
++\$pntcycle;
if (\$pntcycle == 3) {
\$pntcycle = 1;
++\$pnts;
}
\$counter = 0;
while (\$counter <= \$pnts) {
\$counter++;
++\$num;     # This is the more common way to increment a n
+umber
if (\$num == \$lastnumber + 1) { last OUTER }

my \$b = is_prime(\$num);
if (\$b != 0) {\$colr = "white"; \$NumOfPrimes = \$NumOfPrimes
+ + 1;}
if (\$b == 0) {\$colr = "black";}

if (\$order == 1) {\$x = \$x + 1;}
elsif (\$order == 2) {\$y = \$y - 1;}
elsif (\$order == 3) {\$x = \$x - 1; }
elsif (\$order == 4) {\$y = \$y + 1; }

\$c->createText( \$x+\$o, \$y+\$o, -fill => "\$colr", -text => '
+.');
}
}
MainLoop;

BEGIN {
# Cache primes for future use, but using a *hash*, NOT an array!
my %primes = ( 2 => 1 );

sub is_prime {
my (\$num) = @_;

if (exists(\$primes{\$num})) {
return \$primes{\$num};
}

# Only need to calculate up to sqrt(\$num).
# This is VERY important, especially with larger numbers.
# If N is divisible by some factor \$f, less than sqrt(\$N),
# then it's also divisible by some other factor \$k = \$N/\$f
# which MUST be larger than sqrt(\$N), and vice versa.
my \$sqrt = int(sqrt(\$num));

# Check for division by 2 (special-case)
(\$num % 2) or return 0;

# We've tried 2 as a factor, so any other factors must be odd
# (and prime, for that matter).
for (my \$j = 3; \$j <= \$sqrt; \$j += 2) {
if (0 == \$num % \$j) {
# It's NOT a prime.
return 0;
}
}
# Cache the prime number and return '1'
return \$primes{\$num} = 1;
}
}

A couple of other points ...

1. You should use warnings, to get lots of valuable debugging information, like the fact that \$lastnumber was declared twice.
2. my (\$order,\$pntcycle,\$pnts,\$b,\$num,\$p) = (0); likely does NOT do what you want.  It's only setting the value of \$order to zero.  To set them all equal to zero, do something like my \$order = \$my \$pntcycle = my \$pnts = ... = my \$p = 0;, or individually (the way I did above).
3. It's not generally a good idea to make everything global, especially values into and out of a subroutine.  You really should be passing \$num to is_prime(), and returning the value which you assign to \$b.
4. You don't need to quote numbers when you put them into a hash -- \$prime_[\$p] = "\$j"; is better written \$prime_[\$p] = \$j.
5. It's more "Perl-like" to increment a variable with ++\$var.  \$var = \$var + 1 looks too much like, well, BASIC. :-)
6. Many will find your code easier to read if you indent it.

s''(q.S:\$/9=(T1';s;(..)(..);\$..=substr+crypt(\$1,\$2),2,3;eg;print\$..\$/