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