有关素数算法（Jessica1212 接个贴吧）
求素数的方法很多，其中最简单的一种就是除以它之前的所有数（从2开始），如果都不能整除，
它就是一个素数。这个是根据素数的定义求解的，只能被1和它本身整除。
但显然这样的效率是不高的，如果要求1-100内的素数，对每一个数除以之前所有的数，有很多优化的余地。
比如除以素数就可以了，没必要去除以合数，于是加一个表，把之前的结果存储下来，利用空间换取时间。
对于素数的判定，其实只需要判定是否能被 sqrt(n) 以内的素数整除。
感性上讲，对于n，要么是质数，只能被1和自己整除，要么能分解质因数，至少有两个素数因子。 n=p..q
因为不可能p和q都大于sqrt(n)（否则乘积就大于n了），所以只需要判断那个小的素数能不能被n整除就可以了。
这样，把求素数的算法又提高了一步，不过计算中大量的用到除法，除法效率一般比较低。
有一种筛法求素数的算法，把1-n排成一排，从2开始，2的倍数肯定不是素数，去除，剩下的数中下一个是3.
再把3的倍数去除，再下一个是5（4已经去除了），以此类推，最后剩下的数必然是素数，因为
它没有被筛，不是任何一个数的倍数（除了1和自己）。这样只需要很多次加法就可以了。
例如一个求 3000000 以内的素数的程序：
- #include
- #include
- using namespace std;
- const int MAX=3000000;
- char table[MAX];
- void cal_prime()
- {
- memset(table, 1, MAX);
- for (int i = 2; i < MAX; ++i)
- {
- if ( table[i] )
- {
- for ( int j = i+i; j < MAX; j += i )
- {
- table[j] = 0;
- }
- }
- }
- }
- int main()
- {
- clock_t now = clock();
- cal_prime();
- cout << "execution time :" << clock() - now << endl;;
- for ( int i = 2; i < 100; ++i )
- {
- if ( table[i] )
- cout << i << " ";
- }
- return 0;
- }
这算是基本的筛法了，它更是以空间换取时间，因为内存中存的表不只是素数，还有合数的空间，合数比素数多得多。。。
它也有很多优化的余地，比如6，在2的时候筛掉一次。在3的时候又筛掉一次。筛选的时候，一个数之所以能被筛去两次，
它至少是两个质数的倍数，每个质因数筛选一次。通过一定程度上减少重复，可以提升算法的效率。
对于这种算法的改进，有一种更直接的算法，线性筛选，就是对一个合数，就进行一次筛选，极大程度的减少重复计算。
同样条件代码如下：
- #include
- #include
- using namespace std;
- const int MAX=3000000;
- char table[MAX];
- int prime[MAX];
- int num = 0;
- void cal_prime()
- {
- num = 0;
- memset(table, 1, MAX);
- for (int i = 2; i < MAX; ++i)
- {
- if ( table[i] )
- prime[num++] = i;
- for ( int j = 0; j < num && prime[j] * i < MAX; ++j )
- {
- table[ prime[j] * i ] = 0;
- if ( i % prime[j] == 0 ) break;
- }
- }
- }
- int main()
- {
- clock_t now = clock();
- cal_prime();
- cout << "execution time :" << clock() - now << endl;;
- for ( int i = 2; i < 100; ++i )
- {
- if ( table[i] )
- cout << i << " ";
- }
- return 0;
- }
这个算法又多了两倍的空间存储质数，还好这样空间复杂度也是O(n)。
算法中关键点是
if ( i % prime[j] == 0 ) break;
没有这句这个跟筛法就差不多了，主要是防止重复筛除。
这个应该算是求素数最快的确定性算法了，不过感觉用途也不是非常大，除了学习跟玩之外。。。
一般素数的应用在加密领域，利用一个数分解成两个大素数的积非常难的性质，
数论上大数非常大，数组是不可能放下1-n个数的（寻址都不行了）。这点上这个算法还没有
之前直接除的算法实用，最起码一直等还是能出来结果的。。。
不过在应用的时候可以利用费马小定理试探素数，虽然有一定出错的概率，但是概率非常小，
实际中是能够容忍的。
费马小定理虽然证明是错的，但是总还有不少概率是对的。。。
简单说算法是 判断 2^(n-1) % n == 1 是否成立，成立则基本可认为是素数。（要是整数只能算32以内的素数了，
所以先得有个大整数运算的类，没有写过高效的大整数实现，算法也停留在理论 ⊙﹏⊙b汗。。。）
（
费马定理是 a^(n-1) % n == 1 对所有 a < n 的正整数成立。这个小定理算是逆命题特化，不过
是错的。。。
）
另外这个算法出错概率也不小，而且算法也不算是概率算法，因为总是那几个数出错。。。
另有很多改进的算法，加进多次随机基数测试等等，错误概率非常低，而且得看人品。。。
阅读(5468) | 评论(2) | 转发(0) |
