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
#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;
_______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
