[Haskell-beginners] Primes calculation
Sriram Durbha
sriram.durbha at gmail.com
Sat Mar 13 01:32:02 EST 2010
>
> primes [10..30] = [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29] -- not bad
> actually, works as advertised.
>
10 is not prime.
On Fri, Mar 12, 2010 at 7:49 PM, Ozgur Akgun <ozgurakgun at gmail.com> wrote:
> If we try to implement your idea literally we would need one more parameter
> to the function: the list of existing primes.
> I'll call this function primesWRT, since it finds all primes, with respect
> to the second list provided.
>
> primesWRT [] _ = [] -- base case
> primesWRT (x:xs) existing
> -- if all x is not divided by all of the existing primes,
> -- x itself is a prime (wrt 'existing')
> -- add it to the primes list, and the existing primes list for the next
> function call
> | all (\ y -> mod x y /= 0 ) existing = x : primesWRT xs (x:existing)
> -- if x is not prime, check the rest.
> | otherwise = primesWRT xs existing
>
> primes xs = primesWRT xs []
>
>
> Please keep in mind that this function assumes its parameter to be in form
> [2..n]. But this is an assumption coming from your description.
>
> primes [2..20] = [2,3,5,7,11,13,17,19]
> primes [2..30] = [2,3,5,7,11,13,17,19,23,29]
> primes [10..30] = [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29] -- not bad
> actually, works as advertised.
>
> Best,
>
>
> On 12 March 2010 21:14, legajid <legajid at free.fr> wrote:
>
>> Hi,
>> i'm trying to write a function to find all primes from 2 to N.
>>
>>
>> My idea is :
>> take the first number (2)
>> try to find whether it's a multiple of one of all existing primes ([] at
>> first)
>> add 2 to the list of primes
>>
>> take the following number (3)
>> find if multiple of existing primes ([2])
>> add 3 to the list of primes
>>
>> take the following number (4)
>> find if multiple of existing primes ([2, 3])
>> do not add 4 to the list of primes
>>
>> ...
>>
>> take the following number (8)
>> find if multiple of existing primes ([2, 3, 5, 7])
>> do not add 8 to the list of primes
>>
>> take the following number (9)
>> find if multiple of existing primes ([2, 3, 5, 7])
>> do not add 9 to the list of primes (multiple of 3)
>>
>> and so on...
>>
>> So, i would like a function like :
>>
>> f (x : xs) = g x : f xs
>>
>> g would return x if x is prime, [] otherwise
>>
>> But g would use the preceding value of f (list of primes before the
>> calculation for x) that is a result of g itself.
>> f needs g that needs f : what's wrong with my mind ?
>> Perhaps i am still under control of imperative programming ?
>>
>> Thanks for your help,
>>
>> Didier.
>>
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>
>
>
> --
> Ozgur Akgun
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20100313/5ff66c9e/attachment.html
More information about the Beginners
mailing list