1 /*
 2  *  bignum_prime.c
 3  *  BigMath
 4  *
 5  *  Created by Curtis Jones on 2008.03.11.
 6  *  Copyright 2008 __MyCompanyName__. All rights reserved.
 7  *
 8  */
 9 
10 #include "bignum.h"
11 
12 // http://www.luschny.de/math/factorial/index.html
13 
14 /*
15  NOTES
16  
17  Use a bignum_t for the sieve itself - needing only one bit per number.
18  Use a bignum_t for specifying the offset of the bit we want to get/set.
19  
20  Do we need a bignum_prime_sieve_t type?
21  
22  Let limit be the size of the sieve (ie, highest possible prime value).
23  
24  Create a new bignum_t.
25  
26  Initialize the size of the bignum_t to oofm = (limit / sizeof(BASE_TYPE)) + 1.
27   - could this list possibly be half the size, if we assume no even numbers 
28     will be represented in the list? ie, offset / 2? is the memory savings of
29     this approach worth the cost of the additional division operations?
30  
31  Create a results list (ie, each found prime).
32    - can we support this results list notion without allocating a bignum_t for
33      every result?
34    - this results list is going to have to be able to grow. we need an mutable
35      array type....
36  
37  Initialize results list with 2, 3, 5.
38  
39  For each entry in the sieve list (based on mod 60):
40  
41    1. 
42    2. 
43    3. 
44    4. 
45  
46  Start with the lowest number in the sieve list:
47  
48    Take the next number in sieve list still marked prime.
49  
50    Include the number in the results list.
51  
52    Square the number and mark all multiples of that square as non-prime.
53  
54    Loop.
55  
56  
57  
58  */


syntax highlighted by Code2HTML, v. 0.9.1