Numbers (empty) → 0.0
raw patch · 7 files changed
+252/−0 lines, 7 filesdep +basesetup-changed
Dependencies added: base
Files
- Data/Numbers.hs +48/−0
- LICENSE +3/−0
- Numbers.cabal +19/−0
- README +1/−0
- Setup.lhs +4/−0
- lgpl-3.0.txt +165/−0
- test.hs +12/−0
+ Data/Numbers.hs view
@@ -0,0 +1,48 @@+-- | This is an assortment of number theorectic functions. As of now it's not very large or fast, but that should improve over time.+module Data.Numbers where++import Data.List++-- | An infinite list of prime numbers+primes :: [Integer]+primes = 2:3:primes'+ where+ 1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]+ primes' = p : filter isPrime candidates+ divides n p = n `mod` p == 0+ ++-- | Checks whether a number is prime +isPrime :: Integer -> Bool+isPrime n = all (not .(\p-> (n `mod` p) == 0)) $ takeWhile (\p -> p*p <= n) primes++-- | Returns the prime factors for a given number+primeFactors :: Integer -> [Integer] +primeFactors n = primeFactors' n n [] primes where+ -- die Ausgangszahl, der quotient vom letzten mal, die liste der primfaktoren, primzahlen+ primeFactors' n m l (p:ps) + -- die nächste primzahl ist größer als wir? dann sind wir fertig+ | p>n = l+ -- wir sind teilbar durch p? p an die liste vorne dranhängen, quotient merken+ | mo == 0 = primeFactors' n d (p:l) (p:ps)+ -- nicht teilbar? mit der nächsten primzahl von vorne anfangen+ | otherwise = primeFactors' n n l ps where+ (d,mo) = divMod m p+ +-- | Returns the number of divisors of a number. Uses <http://mathschallenge.net/index.php?section=faq&ref=number/number_of_divisors>+numOfFactors :: Integer -> Int+numOfFactors n = product (map ((+1).length) (group (primeFactors n)))++-- | Returns the sum of the factors of a number+factorSum :: Integer -> Integer+factorSum = product.(map (\p@(x:xs) -> (product p * x -1) `div` (x-1))).(group.primeFactors)++-- | Returns the factors of a number+factors :: Integer -> [Integer]+factors n = 1:factors' n [] [2..] where+ factors' n l (m:ms) + | m*m==n= m:l+ | m*m>n = l+ | r == 0 = factors' n (d:m:l) ms+ | otherwise = factors' n l ms where+ (d,r) = divMod n m
+ LICENSE view
@@ -0,0 +1,3 @@+Copyright 2009 Adrian Neumann++You may use this library under the terms of the LGPL, which is included in the file lgpl-3.0.txt
+ Numbers.cabal view
@@ -0,0 +1,19 @@+Name: Numbers+Version: 0.0+Cabal-Version: >= 1.2+Synopsis: An assortment of number theoretic functions+Description: Functions for finding prime numbers, checking whether a number is prime, finding the factors of a number etc.+License: LGPL+License-file: LICENSE+Author: Adrian Neumann+Category: Algorithms, Number Theory+Maintainer: aneumann@inf.fu-berlin.de+stability: alpha+build-type: Simple+extra-source-files: README, test.hs, lgpl-3.0.txt++Library+ exposed-modules: Data.Numbers+ build-depends: + base+ GHC-Options: -O2
+ README view
@@ -0,0 +1,1 @@+This is an assortment of number theorectic functions. As of now it's not very large or fast, but that should improve over time.
+ Setup.lhs view
@@ -0,0 +1,4 @@+#! /usr/bin/env runhaskell+ +> import Distribution.Simple+> main = defaultMain
+ lgpl-3.0.txt view
@@ -0,0 +1,165 @@+ GNU LESSER GENERAL PUBLIC LICENSE+ Version 3, 29 June 2007++ Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed.+++ This version of the GNU Lesser General Public License incorporates+the terms and conditions of version 3 of the GNU General Public+License, supplemented by the additional permissions listed below.++ 0. Additional Definitions. ++ As used herein, "this License" refers to version 3 of the GNU Lesser+General Public License, and the "GNU GPL" refers to version 3 of the GNU+General Public License.++ "The Library" refers to a covered work governed by this License,+other than an Application or a Combined Work as defined below.++ An "Application" is any work that makes use of an interface provided+by the Library, but which is not otherwise based on the Library.+Defining a subclass of a class defined by the Library is deemed a mode+of using an interface provided by the Library.++ A "Combined Work" is a work produced by combining or linking an+Application with the Library. The particular version of the Library+with which the Combined Work was made is also called the "Linked+Version".++ The "Minimal Corresponding Source" for a Combined Work means the+Corresponding Source for the Combined Work, excluding any source code+for portions of the Combined Work that, considered in isolation, are+based on the Application, and not on the Linked Version.++ The "Corresponding Application Code" for a Combined Work means the+object code and/or source code for the Application, including any data+and utility programs needed for reproducing the Combined Work from the+Application, but excluding the System Libraries of the Combined Work.++ 1. Exception to Section 3 of the GNU GPL.++ You may convey a covered work under sections 3 and 4 of this License+without being bound by section 3 of the GNU GPL.++ 2. Conveying Modified Versions.++ If you modify a copy of the Library, and, in your modifications, a+facility refers to a function or data to be supplied by an Application+that uses the facility (other than as an argument passed when the+facility is invoked), then you may convey a copy of the modified+version:++ a) under this License, provided that you make a good faith effort to+ ensure that, in the event an Application does not supply the+ function or data, the facility still operates, and performs+ whatever part of its purpose remains meaningful, or++ b) under the GNU GPL, with none of the additional permissions of+ this License applicable to that copy.++ 3. Object Code Incorporating Material from Library Header Files.++ The object code form of an Application may incorporate material from+a header file that is part of the Library. You may convey such object+code under terms of your choice, provided that, if the incorporated+material is not limited to numerical parameters, data structure+layouts and accessors, or small macros, inline functions and templates+(ten or fewer lines in length), you do both of the following:++ a) Give prominent notice with each copy of the object code that the+ Library is used in it and that the Library and its use are+ covered by this License.++ b) Accompany the object code with a copy of the GNU GPL and this license+ document.++ 4. Combined Works.++ You may convey a Combined Work under terms of your choice that,+taken together, effectively do not restrict modification of the+portions of the Library contained in the Combined Work and reverse+engineering for debugging such modifications, if you also do each of+the following:++ a) Give prominent notice with each copy of the Combined Work that+ the Library is used in it and that the Library and its use are+ covered by this License.++ b) Accompany the Combined Work with a copy of the GNU GPL and this license+ document.++ c) For a Combined Work that displays copyright notices during+ execution, include the copyright notice for the Library among+ these notices, as well as a reference directing the user to the+ copies of the GNU GPL and this license document.++ d) Do one of the following:++ 0) Convey the Minimal Corresponding Source under the terms of this+ License, and the Corresponding Application Code in a form+ suitable for, and under terms that permit, the user to+ recombine or relink the Application with a modified version of+ the Linked Version to produce a modified Combined Work, in the+ manner specified by section 6 of the GNU GPL for conveying+ Corresponding Source.++ 1) Use a suitable shared library mechanism for linking with the+ Library. A suitable mechanism is one that (a) uses at run time+ a copy of the Library already present on the user's computer+ system, and (b) will operate properly with a modified version+ of the Library that is interface-compatible with the Linked+ Version. ++ e) Provide Installation Information, but only if you would otherwise+ be required to provide such information under section 6 of the+ GNU GPL, and only to the extent that such information is+ necessary to install and execute a modified version of the+ Combined Work produced by recombining or relinking the+ Application with a modified version of the Linked Version. (If+ you use option 4d0, the Installation Information must accompany+ the Minimal Corresponding Source and Corresponding Application+ Code. If you use option 4d1, you must provide the Installation+ Information in the manner specified by section 6 of the GNU GPL+ for conveying Corresponding Source.)++ 5. Combined Libraries.++ You may place library facilities that are a work based on the+Library side by side in a single library together with other library+facilities that are not Applications and are not covered by this+License, and convey such a combined library under terms of your+choice, if you do both of the following:++ a) Accompany the combined library with a copy of the same work based+ on the Library, uncombined with any other library facilities,+ conveyed under the terms of this License.++ b) Give prominent notice with the combined library that part of it+ is a work based on the Library, and explaining where to find the+ accompanying uncombined form of the same work.++ 6. Revised Versions of the GNU Lesser General Public License.++ The Free Software Foundation may publish revised and/or new versions+of the GNU Lesser General Public License from time to time. Such new+versions will be similar in spirit to the present version, but may+differ in detail to address new problems or concerns.++ Each version is given a distinguishing version number. If the+Library as you received it specifies that a certain numbered version+of the GNU Lesser General Public License "or any later version"+applies to it, you have the option of following the terms and+conditions either of that published version or of any later version+published by the Free Software Foundation. If the Library as you+received it does not specify a version number of the GNU Lesser+General Public License, you may choose any version of the GNU Lesser+General Public License ever published by the Free Software Foundation.++ If the Library as you received it specifies that a proxy can decide+whether future versions of the GNU Lesser General Public License shall+apply, that proxy's public statement of acceptance of any version is+permanent authorization for you to choose that version for the+Library.
+ test.hs view
@@ -0,0 +1,12 @@+import Data.Numbers++import Data.List++test_primes = take 1000 primes == take 1000 check where+ check = sieve [2..]+ where sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0]+ + +test_isprime = and $ map (isPrime) $ take 1000 primes++test_primeFactors = let l = take 5 primes in sort (primeFactors (product l)) == sort l