[PD] prime numbers

[Mathieu Bouchard]

On Sun, 12 Sep 2010, Claude Heiland-Allen wrote:

> A prime number has exactly two factors (1 and itself).  I attached an 
> abstraction to generate a list of all factors of a number, which could 
> be used to see if a number is prime (inefficiently).

This slightly modified version runs in time O(sqrt(n)) instead of O(n)...

I'm not not counting the step of putting the factors together as list, but 
if I did, we'd have to write it as O(sqrt(n)+factors^2) and O(n+factors^2) 
respectively. This could be fixed using the usual messagebox trick.

  _______________________________________________________________________
| Mathieu Bouchard ------------------------------ Villeray, Montréal, QC
-------------- next part --------------
#N canvas 199 72 341 412 10;
#X obj 24 12 inlet;
#X obj 24 51 t b f f b;
#X obj 24 32 max 1;
#X obj 31 268 list prepend;
#X obj 31 288 t a a;
#X obj 24 316 list append;
#X obj 24 373 outlet;
#X obj 31 112 until;
#X obj 31 145 f;
#X obj 59 145 + 1;
#X obj 31 165 t f f;
#X obj 54 186 swap;
#X obj 54 207 mod;
#X obj 54 227 ==;
#X obj 31 248 spigot;
#X msg 71 115 1;
#X obj 31 74 sqrt;
#X obj 156 242 swap;
#X obj 156 265 /;
#X obj 156 284 list append;
#X obj 156 304 t a a;
#X obj 24 336 list append;
#X obj 119 218 moses;
#X obj 31 93 t f f;
#X connect 0 0 2 0;
#X connect 1 0 5 0;
#X connect 1 1 16 0;
#X connect 1 2 11 1;
#X connect 1 2 17 1;
#X connect 1 3 3 1;
#X connect 1 3 15 0;
#X connect 1 3 19 1;
#X connect 2 0 1 0;
#X connect 3 0 4 0;
#X connect 4 0 5 1;
#X connect 4 1 3 1;
#X connect 5 0 21 0;
#X connect 7 0 8 0;
#X connect 8 0 9 0;
#X connect 8 0 10 0;
#X connect 9 0 8 1;
#X connect 10 0 14 0;
#X connect 10 1 11 0;
#X connect 11 0 12 0;
#X connect 11 1 12 1;
#X connect 12 0 13 0;
#X connect 13 0 14 1;
#X connect 14 0 3 0;
#X connect 14 0 22 0;
#X connect 15 0 8 1;
#X connect 16 0 23 0;
#X connect 17 0 18 0;
#X connect 17 1 18 1;
#X connect 18 0 19 0;
#X connect 19 0 20 0;
#X connect 20 0 19 1;
#X connect 20 1 21 1;
#X connect 21 0 6 0;
#X connect 22 0 17 0;
#X connect 23 0 7 0;
#X connect 23 1 22 1;