Quiz: Primes in the BCL... part 2
Some good comments on my BCL prime quiz… but still one unanswered question (at the end)…
Thomas Woelfer quickly got that the place in the BCL for generating prime numbers is in Hashtable.cs and Eric Wilson does a good job explaining why…
Specifically, primes are used when the size of a hash table must be increased because of the load has reached a certain level. The size of the hashtable is increased such that the number of buckets in the hashtable increases to the smallest prime number that is larger than twice the current number of Hashtable buckets.
The reason for this is two fold. Using a prime number of buckets reduces the effect of clustering in the hashtable (having multiple keys hash to the same location). The size is at least doubled because by doing that the BCL can insure that over a series of N insert, the total time for all inserts takes no more than O(log(N)) total time
And I really love the reference to Juan Felipe Machado gives: “Knuth's Art of Computer Programming, Vol. 3, p. 528-9”, clearly a desktop reference favorite. How long before it is common place to quote the SLAR v1, pp 239-243 ;-)
In addition, Norman Headlam gives some of the code in question, but the method I was really talking about is this one…
00149 private bool Primep (int candidate) {
00150 if ((candidate & 1) != 0) {
00151 for (int divisor = 3; divisor < (int)Math.Sqrt (candidate); divisor+=2){
00152 if ((candidate % divisor) == 0)
00153 return false;
00154 }
00155 return true;
00156 }
00157 else {
00158 return (candidate == 2);
00159 }
00160 }
00161
A few of you pointed out some interesting issues, but not what I was looking for… the problem is in the code above and it results in some numbers being return as prime that are not really prime…The bug can be found for “normal” input ranges such as [1-100].
