12 Sep
2010
12 Sep
'10
2:55 a.m.
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