Talk:Primality by trial division: Difference between revisions
(so am I allowed to recurse?) |
(How's that?) |
||
| Line 4: | Line 4: | ||
:Why not just say "Use trial division to test each number"? --[[User:Mwn3d|Mwn3d]] 15:19, 4 February 2008 (MST) |
:Why not just say "Use trial division to test each number"? --[[User:Mwn3d|Mwn3d]] 15:19, 4 February 2008 (MST) |
||
:: Even that isn't particularly precise. Should I do trial-division by every integer 2 through n-1? Or am I allowed to factor only up to (sqrt(n)) which is obviously sufficient but introduces the added complexity of invoking a square root. So is it still the "simplest" solution? Is simplicity preferred? Actually it would be entirely sufficient to trial-factor only by all <i>prime</i> numbers up to sqrt(n) which immediately leads to a very elegant recursive implementation. Which I'm pretty sure isn't what the creator of the task had in mind ;-) but which is entirely allowed when you just say "use trial division"... [[User:Sgeier|Sgeier]] 19:21, 4 February 2008 (MST) |
:: Even that isn't particularly precise. Should I do trial-division by every integer 2 through n-1? Or am I allowed to factor only up to (sqrt(n)) which is obviously sufficient but introduces the added complexity of invoking a square root. So is it still the "simplest" solution? Is simplicity preferred? Actually it would be entirely sufficient to trial-factor only by all <i>prime</i> numbers up to sqrt(n) which immediately leads to a very elegant recursive implementation. Which I'm pretty sure isn't what the creator of the task had in mind ;-) but which is entirely allowed when you just say "use trial division"... [[User:Sgeier|Sgeier]] 19:21, 4 February 2008 (MST) |
||
==new description== |
|||
I fixed up the description. I tried to be more specific, but didn't rule out recursion. If you use recursion make sure you note it and add the task to the [[:Category:Recursion|recursion category]] --[[User:Mwn3d|Mwn3d]] 19:46, 4 February 2008 (MST) |
|||
Revision as of 02:46, 5 February 2008
"simplest"?
The task states "Implement the simplest primality test, using trial division." I'd like to submit that any such statement is always inappropriate at this wiki, as it presumes knowledge what method of solving some task is "the simplest" in all conceivable languages. There may well be languages where some other method might be "simpler", especially given that "simple" is not exactly a particularly well-defined term. In particular in the sense of complexity defined through the computational resources required to express the result, a Miller-test might well be "simpler" than trial-factoring.Sgeier 13:22, 4 February 2008 (MST)
- Why not just say "Use trial division to test each number"? --Mwn3d 15:19, 4 February 2008 (MST)
- Even that isn't particularly precise. Should I do trial-division by every integer 2 through n-1? Or am I allowed to factor only up to (sqrt(n)) which is obviously sufficient but introduces the added complexity of invoking a square root. So is it still the "simplest" solution? Is simplicity preferred? Actually it would be entirely sufficient to trial-factor only by all prime numbers up to sqrt(n) which immediately leads to a very elegant recursive implementation. Which I'm pretty sure isn't what the creator of the task had in mind ;-) but which is entirely allowed when you just say "use trial division"... Sgeier 19:21, 4 February 2008 (MST)
new description
I fixed up the description. I tried to be more specific, but didn't rule out recursion. If you use recursion make sure you note it and add the task to the recursion category --Mwn3d 19:46, 4 February 2008 (MST)