第一章 素数判定法现状

现在，确定性素数判定法已经有很多种，常用的有试除法、威廉斯方法、艾德利曼和鲁梅利法。它们的适用范围各不相同，威廉斯方法比较适合10^20到10^50之间的数，艾德利曼和鲁梅利法适合大于10^50的数，对于32位机器数，由于都小于10^10，所以一般都用试除法来判定。

也许有人会问：“你为什么没有提马宁德拉.阿格拉瓦法呢？不是有人说它是目前最快的素数判定法吗？” 其实这是一个很大的误解，阿格拉瓦法虽然是log(n)的多项式级算法，但目前只有理论上的意义，根本无法实用，因为它的时间复杂度是O(log(n)^12)，这个多项式的次数太高了。就拿最慢的试除法跟它来比吧，试除法的时间复杂度为O(n^(1/2)*log(n)^2)，当n = 16时，log(n)^12 = 16777216，而n^(1/2)*log(n)^2 = 64，你看相差有多么大！如果要让两者速度相当，即log(n)^12 = n^(1/2)*log(n)^2，得出n = 10^43.1214，此时需要进行的运算次数为log(n)^12 = 10^25.873（注意：本文中log（）函数缺省以2为底），这样的运算次数在一台主频3GHz的计算机上运行也要10^8.89707年才能运行完，看来我们这辈子是别指望看到阿格拉瓦法比试除法快的这一天啦！

除了这些确定性素数判定法外，还有基于概率的非确定性素数判定法，最常用的就是米勒-拉宾法。

对于32位机器数（四则运算均为常数时间完成），试除法的时间复杂度是O(n^(1/2))，而米勒-拉宾法的时间复杂度只有O(log(n))。所以后者要比前者快得多，但是由于米勒-拉宾法的非确定性，往往我们在需要确定解时仍然要依靠速度较慢的试除法。那是否可以通过扩展米勒-拉宾法，来找到一种更快的确定性素数判定法呢？结论是肯定的，本文就带你一起寻找这样一种方法。

第二章 2-伪素数表的生成

既然要扩展米勒-拉宾法，那首先我们应该知道为什么米勒-拉宾法是个非确定性素数判定法？答案很简单，由于伪素数的存在。由于米勒-拉宾法使用费尔马小定理的逆命题进行判断，而该逆命题对极少数合数并不成立，从而产生误判，这些使费尔马小定理的逆命题不成立的合数就是伪素数。为了研究伪素数，我们首先需要生成伪素数表，原理很简单，就是先用筛法得出一定范围内的所有素数，然后逐一判定该范围内所有合数是否使以2为底数的费尔马小定理的逆命题不成立，从而得出该范围内的2-伪素数表。我的程序运行了100分钟，得出了32位机器数范围内的2-伪素数表，如下：

341

561

645

1105

1387

1729

1905

2047

2465

2701

...

...

...

4286813749

4288664869

4289470021

4289641621

4289884201

4289906089

4293088801

4293329041

4294868509

4294901761

（共10403个，由于篇幅所限，中间部分省略。）

第三章 寻找2-伪素数的最小可判定底数

对于2-伪素数表的每一个伪素数，寻找最小的可以判定它们是合数的底数，我把这个底数称之为最小可判定底数。特别地，对于绝对伪素数，它的最小质因子即是它的最小可判定底数。由于已经证明了绝对伪素数至少有三个质因子，所以这个最小质因子一定不大于n^(1/3)。下面就是我找到的最小可判定底数列表：

341     3

561     3

645     3

1105    5

1387    3

1729    7

1905    3

2047    3

2465    5

2701    5

...

...

...

4286813749      3

4288664869      3

4289470021      5

4289641621      3

4289884201      3

4289906089      3

4293088801      3

4293329041      3

4294868509      7

4294901761      3

通过统计这个列表，我发现了一个规律，那就是所有的最小可判定底数都不大于n^(1/3)，由前述可知，对于绝对伪素数，这个结论显然成立。而对于非绝对伪素数，虽然直观上觉得它应该比绝对伪素数好判定出来，但是我无法证明出它的最小可判定底数都不大于n^(1/3)。不过没关系，这个问题就作为一个猜想留给数学家来解决吧，更重要的是我已经通过实验证明了在32位机器数范围内这个结论成立。

我们还有没有更好的方法来进一步减小最小可判定底数的范围呢？有的！我们可以在计算平方数时进行二次检测，下面是进行了二次检测后重新计算的最小可判定底数列表：

341     2

561     2

645     2

1105    2

1387    2

1729    2

1905    2

2047    3

2465    2

2701    2

...

...

...

4286813749      2

4288664869      2

4289470021      2

4289641621      2

4289884201      2

4289906089      2

4293088801      2

4293329041      2

4294868509      2

4294901761      3

很显然，二次检测是有效果的，经过统计，我发现了新的规律，那就是经过二次检测后所有的最小可判定底数都不大于n^(1/6)，真的是开了一个平方呀，哈哈！这个结论的数学证明仍然作为一个猜想留给数学家们吧。我把这两个猜想叫做费尔马小定理可判定上界猜想。而我已经完成了对32位机器数范围内的证明。

通过上面总结的规律，我们已经可以设计出一个对32位机器数进行素数判定的 O(n^(1/6)*log(n)) 的确定性方法。但是这还不够，我们还可以优化，因为此时的最小可判定底数列表去重后只剩下了5个数（都是素数）：{2,3,5,7,11}。天哪，就是前5个素数，这也太容易记忆了吧。

不过在实现算法时，需要注意这些结论都是在2-伪素数表基础上得来的，也就是说不管如何对2的判定步骤必不可少，即使当2>n^(1/6)时。

还有一些优化可以使用，经过实验，当n>=7^6时，可以不进行n^(1/6)上界限制，而固定地用{2,5,7,11}去判定，也是100%正确的。这样就可以把判定次数降为4次以下，而每次判定只需要进行4log(n)次乘除法（把取余运算也看作除法），所以总的计算次数不会超过16log(n)。经过实验，最大的计算次数在n=4294967291时出现，为496次。

自己写了个随机化素数判定算法：
s越大，稳定性越好，但效率会低点。原作者有更好的判定算法，对作者表示感谢。。 对自定义类型到string的示例

 

Reference Type 和 Pointer Type

所谓左值（lValue）：是用来代表某个对象的一个东西。如果p是指向类型为T的某个对象，那么表达式*p不能只是返回类型为T的对象，而必须是返回一个lValue（左值）。

   平时总是拿起*p就直接赋值（对于简单基本类型，例如int *p = &I ;  *p=3），没想什么*p返回左值那么多。但是当在自定义类中重栽*运算符的时候，我们就要特别小心，要注意到这点，返回为T& 才对。

言规正传

iterator_traits的某些机制所蕴涵的意义十分微妙而深远，不过它的实现却不是很复杂，不过这些东西看起来比较容易看懂，真正能够灵活使用就需要花时间领悟了，为什么会采取这种方法解决问题，和其它的方法对比有什么好处和提高？这种明白这些问题才算掌握了trait的实质。

template< class Iterator>

struct iterator_traits

{

typedef   typename Iterator::iterator_category   iterator_category;

typedef   typename Iterator::value_type        value_type;

typedef   typename Iterator::difference_type    difference_type;

typedef   typename Iterator::pointer           pointer;

typedef   typename Iterator::reference         reference    ;

};

template< class T>

struct iterator_traits

{

typedef   random_access_iterator_tag   iterator_category;

typedef   T        value_type;

typedef   ptrdiff_t    difference_type;

typedef   T*           pointer;

typedef   T&         reference    ;

};

template< class T>

struct iterator_traits

{

typedef   random_access_iterator_tag   iterator_category;

typedef   T        value_type;

typedef   ptrdiff_t    difference_type;

typedef   T*           pointer;

typedef   T&         reference    ;

};

当你定义一个自己的算法，你需要关注这个机制，下面两个理由就是你可能要用到iterator_traits：

①     你必须返回某值，或者是申明临时变量，而其它型别与iterator的value type 或者different type或者reference type 或者pointer type一致。

②     你的算法类似与advance，必须根据iterator的分类来决定不同的实现方法（提高效率，在编译时候进行判断而不是在运行的时候进行判断），没有traits机制，你只好在‘一般化但是没效率’或者‘有效率但是过度狭隘’中进行抉择。

当定义一个Iterator 类，就得在改类中定义五个嵌套的类型，如上面的五个所示。要不然就得针对你的Iterator类，明白的令iterator_traits为Iterator特化，就像iterator_traits要明白的针对指针而特化一样。第一种做法总是比较简单，尤其是STL的一个辅助类，base class iterator，让事情变得更简单了。

template< class Category,

class Value,

class Distance =ptrdiff_t,

class Pointer = Value*,

class Reference = Value &

>

struct iterator

{

typedef Category iterator_category;

typedef Value      value_type;

typedef Distance difference_type;

typedef Pointer     pointer;

typedef Reference   reference;

};

     为了确保iterator_traits能够对新的iterator class有适当的定义，最简单的方法就是从iterator类派生自己的iterator。基类iterator不含任何成员函数和成员变量，所以继承不存在额外的开销。

说来惭愧，使用了很久Visual Stdio 2003了，只知道MFC升级到了7.0，ATL也升级到了7.0，对于这两个经典的类库做了一些研究，但一直没有注意C++标准库的变化。

     今天尝试的使用了stdext::hash_map这个库，果然不错。下面写下一些心得。

     hash_map类在头文件hash_map中，和所有其它的C++标准库一样，头文件没有扩展名。如下声明：

          #include <hash_map>
          using namespace std;
          using namespace stdext;

     hash_map是一个聚合类，它继承自_Hash类，包括一个vector，一个list和一个pair，其中vector用于保存桶，list用于进行冲突处理，pair用于保存key->value结构，简要地伪码如下：

          class hash_map<class _Tkey, class _Tval>
          {
          private:
               typedef pair<_Tkey, _Tval> hash_pair;
               typedef list<hash_pair>    hash_list;
               typedef vector<hash_list>  hash_table;
          };

     当然，这只是一个简单模型，C++标准库的泛型模版一向以嵌套复杂而闻名，初学时看类库，无疑天书啊。微软的hash_map类还聚合了hash_compare仿函数类，hash_compare类里有聚合了less仿函数类，乱七八糟的。

     下面说说使用方法：

     一、简单变量作为索引：整形、实性、指针型
     其实指针型也就是整形，算法一样。但是hash_map会对char*, const char*, wchar_t*, const wchar_t*做特殊处理。
     这种情况最简单，下面代码是整形示例：
            hash_map<int, int> IntHash;
            IntHash[1] = 123;
            IntHash[2] = 456;

            int val = IntHash[1];
            int val = IntHash[2];
     实型和指针型用法和整形一样，原理如下：
     1、使用简单类型作索引声明hash_map的时候，不需要声明模版的后两个参数（最后一个参数指名hash_map节点的存储方式，默认为pair，我觉得这就挺好，没必要修改），使用默认值就好。
     2、对于除过字符串的其它简单类型，hash_map使用模版函数 size_t hash_value(const _Kty& _Keyval) 计算hash值，计算方法是经典的掩码异或法，自动溢出得到索引hash值。微软的工程师也许开了一个玩笑，这个掩码被定义为0xdeadbeef(死牛肉，抑或是某个程序员的外号）。
     3、对于字符串指针作索引的时候，使用定类型函数inline size_t hash_value(const char *_Str)或inline size_t hash_value(const wchar_t *_Str)计算hash值，计算方法是取出每一个字符求和，自动溢出得到hash值。对于字符串型的hash索引，要注意需要自定义less仿函数。
     因为我们有理由认为，人们使用hash表进行快速查找的预期成本要比在hash表中插入的预期成本低得多，所以插入可以比查找昂贵些；基于这个假设，hash_map在有冲突时，插入链表是进行排序插入的，这样在进行查询冲突解决的时候就能够更快捷的找到需要的索引。
     但是，基于泛型编程的原则，hash_map也有理由认为每一种类型都支持使用"<"来判别两个类型值的大小，这种设计恰好让字符串类型无所适从，众所周知，两个字符串指针的大小并不代表字符串值的大小。见如下代码：
          hash_map<const char*, int> CharHash;
          CharHash["a"] = 123;
          CharHash["b"] = 456;

          char szInput[64] = "";
          scanf("%s", szInput);

          int val = CharHash[szInput];

     最终的结果就是无论输入任何字符串，都无法找到对应的整数值。因为输入的字符串指针是szInput指针，和"a"或"b"字符串常量指针的大小是绝对不会相同。解决方法如下：
     首先写一个仿函数CharLess，继承自仿函数基类binary_function（当然也可以不继承，这样写只是符合标准，而且写起来比较方便，不用被类似于指针的指针和指针的引用搞晕。

          struct CharLess : public binary_function<const char*, const char*, bool>
          {
          public:
               result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
               {
                    return(stricmp(_Left, _Right) < 0 ? true : false);
               }
          };

     很好，有了这个仿函数，就可以正确的使用字符串指针型hash_map了。如下：

          hash_map<const char*, int, hash_compare<const char*, CharLess> > CharHash;
          CharHash["a"] = 123;
          CharHash["b"] = 456;

          char szInput[64] = "";
          scanf("%s", szInput);

          int val = CharHash[szInput];
     
     现在就可以正常工作了。至此，简单类型的使用方法介绍完毕。

     二、用户自定义类型：比如对象类型，结构体。
     这种情况比价复杂，我们先说简单的，对于C++标准库的string类。
     
     庆幸的是，微软为basic_string（string类的基类）提供了hash方法，这使得使用string对象做索引简单了许多。值得注意（也值得郁闷）的是，虽然支持string的hash，string类却没有重载比较运算符，所以标准的hash_compare仿函数依旧无法工作。我们继续重写less仿函数。
         
          struct string_less : public binary_function<const string, const string, bool>
          {
          public:
               result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
               {
                    return(_Left.compare(_Right) < 0 ? true : fase);
               }
          };
           
     好了，我们可以书写如下代码：
           
          hash_map<string, int, hash_compare<string, string_less> > StringHash;
          StringHash["a"] = 123;
          StringHash["b"] = 456;

          string strKey = "a";

          int val = CharHash[strKey];
     
     这样就可以了。
     
     对于另外的一个常用的字符串类CString（我认为微软的CString比标准库的string设计要洒脱一些）更加复杂一些。很显然，标准库里不包含对于CString的支持，但CString却重载了比较运算符（郁闷）。我们必须重写hash_compare仿函数。值得一提的是，在Virtual Stdio 2003中，CString不再是MFC的成员，而成为ATL的成员，使用#include <atlstr.h>就可以使用。我没有采用重写hash_compare仿函数的策略，而仅仅是继承了它，在模版库中的继承是没有性能损耗的，而且能让我偷一点懒。
     首先重写一个hash_value函数：
     
          inline size_t CString_hash_value(const CString& str)
          {
               size_t value = _HASH_SEED;
               size_t size  = str.GetLength();
               if (size > 0) {
                    size_t temp = (size / 16) + 1;
                    size -= temp;
                    for (size_t idx = 0; idx <= size; idx += temp) {
                         value += (size_t)str[(int)idx];
                    }
               }
               return(value);
          }
     
     其次重写hash_compare仿函数：
     
          class CString_hash_compare : public hash_compare<CString>
          {
          public:
               size_t operator()(const CString& _Key) const
               {
                    return((size_t)CString_hash_value(_Key));
               }
  
               bool operator()(const CString& _Keyval1, const CString& _Keyval2) const
               {
                    return (comp(_Keyval1, _Keyval2));
               }
          };
           
     上面的重载忽略了基类对于less仿函数的引入，因为CString具备比较运算符，我们可以使用默认的less仿函数，在这里映射为comp。好了，我们可以声明新的hash_map对象如下：

          hash_map<CString, int, CString_hash_compare> CStringHash;

     其余的操作一样一样的。

     下来就说说对于自定义对象的使用方法：首先定义
     
          struct IHashable
          {
               virtual unsigned long hash_value() const = 0;
               virtual bool operator < (const IHashable& val) const = 0;
               virtual IHashable& operator = (const IHashable& val) = 0;
          };
     
     让我们自写的类都派生自这里，有一个标准，接下来定义我们的类：
     
          class CTest : public IHashable
          {
          public:
               int m_value;
               CString m_message;
          public:
               CTest() : m_value(0)
               {
               }
           
               CTest(const CTest& obj)
               {
                    m_value = obj.m_value;
                    m_message = obj.m_message;
               }
          public:
               virtual IHashable& operator = (const IHashable& val)
               {
                    m_value   = ((CTest&)val).m_value;
                    m_message = ((CTest&)val).m_message;
                    return(*this);
               }
           
               virtual unsigned long hash_value() const
               {
                    // 这里使用类中的m_value域计算hash值，也可以使用更复杂的函数计算所有域总的hash值
                    return(m_value ^ 0xdeadbeef 
               }
           
               virtual bool operator < (const IHashable& val) const
               {
                    return(m_value < ((CTest&)val).m_value);
               }
          };
     
     用这个类的对象做为hash索引准备工作如下，因为接口中规定了比较运算符，所以这里可以使用标准的less仿函数，所以这里忽略：
     
          template<class _Tkey>
          class MyHashCompare : public hash_compare<_Tkey>
          {
          public:
               size_t operator()(const _Tkey& _Key) const
               {
                    return(_Key.hash_value());
               }
           
               bool operator()(const _Tkey& _Keyval1, const _Tkey& _Keyval2) const
               {
                    return (comp(_Keyval1, _Keyval2));
               }
          };
           
     下来就这样写：
     
          CTest test;
          test.m_value = 123;
          test.m_message = "This is a test";
     
          MyHash[test] = 2005;
           
          int val = MyHash[test];
     
     可以看到正确的数字被返回。
     
     三、关于hash_map的思考：
     
     1、性能分析：采用了内联代码和模版技术的hash_map在效率上应该是非常优秀的，但我们还需要注意如下几点：
     
     * 经过查看代码，字符串索引会比简单类型索引速度慢，自定义类型索引的性能则和我们选择hash的内容有很大关系，简单为主，这是使用hash_map的基本原则。
     * 可以通过重写hash_compair仿函数，更改里面关于桶数量的定义，如果取值合适，也可以得到更优的性能。如果桶数量大于10，则牢记它应该是一个质数。
     * 在自定义类型是，重载的等号（或者拷贝构造）有可能成为性能瓶颈，使用对象指针最为索引将是一个好的想法，但这就必须重写less仿函数，理由同使用字符串指针作为索引。

        想自己开始学语言的时候，因为根本不知道什么书好，所以看到基本是一些国内的，水平一般的书，如果你刚开始学c or c++,推荐c++创始人写的<<the c++ programming language>>,即使是学有所成的人，再看此书也有很大收获我想，慢慢品味，会有收获的。。。以后我会将自己学习此书的笔记写在此，各位路过的大牛指点指点。。。^_^