Difference between revisions of "Talk:Prime numbers"
m |
(...you're right, you know...) |
||
| Line 12: | Line 12: | ||
why not use <hask>(\x -> n > x*x)</hask> --[[User:JohannesAhlmann|Johannes Ahlmann]] 21:18, 5 February 2007 (UTC) |
why not use <hask>(\x -> n > x*x)</hask> --[[User:JohannesAhlmann|Johannes Ahlmann]] 21:18, 5 February 2007 (UTC) |
||
| + | |||
| + | LOL! That is ''indeed'' what I meant. |
||
| + | |||
| + | It turns out my comment above is correct - the <hask>takeWhile</hask> filtering in <hask>factors</hask> is in fact unecessary. The function works just fine without it. (Notice I have made some edits to correct the multiple bugs in the <hask>primes</hask> function. Oops!) |
||
| + | |||
| + | Now the only use of <hask>takeWhile</hask> is in the <hask>is_prime</hask> function, which could be changed to 'give up' the search a lot faster and hence confirm large primes with much less CPU time and RAM usage. Maybe I'll wrap my brain around that later. |
||
| + | |||
| + | [[User:MathematicalOrchid|MathematicalOrchid]] 10:17, 6 February 2007 (UTC) |
||
Revision as of 10:17, 6 February 2007
Here's an interesting question: will the program go faster if we replace all those (n >) expressions with (\x -> floor (sqrt n) > x)?
On one hand, a composite integer cannot possess a factor greater than its square root.
On the other hand, since the list we're looking through contains all possible prime numbers, we are guaranteed to find a factor or an exact match eventually, so do we need the takeWhile at all?
Throwing this over to somebody with a bigger brain than me...
MathematicalOrchid 16:41, 5 February 2007 (UTC)
a composite can indeed have factors greater than its square root, and indeed most do. what you mean is that a composite will definitely have at least one factor smaller-equal than its square root.
why not use (\x -> n > x*x) --Johannes Ahlmann 21:18, 5 February 2007 (UTC)
LOL! That is indeed what I meant.
It turns out my comment above is correct - the takeWhile filtering in factors is in fact unecessary. The function works just fine without it. (Notice I have made some edits to correct the multiple bugs in the primes function. Oops!)
Now the only use of takeWhile is in the is_prime function, which could be changed to 'give up' the search a lot faster and hence confirm large primes with much less CPU time and RAM usage. Maybe I'll wrap my brain around that later.
MathematicalOrchid 10:17, 6 February 2007 (UTC)