我们经常跟素数打交道, 我们知道素数的各种验证算法, 但是是否存在素数的生成算法呢?
事实上, 我们有许多可以生成素数的算法, 但是, 由于这些算法的效率极低, 我们基本上不会使用这些算法.
方法一: 素数编码
设 pn 是第n个素数, Sierpinski 先生曾经定义了这样一个常量:
若定义[x]为一取下整函数, 即[x]表示不大于x的最大整数. 那么我们有:
对于这一类方法, 当把相关常量计算出来时才有实际价值, 这似乎不太可能.
方法二: 利用 Wilson 原理
Willans 先生这样定义了函数 pi(x) :
那么, 对于大于2的任意整数n, 我们有:
这个方法虽然比前一个更具体, 但是, 其中涉及到了很大的数, 要应用到实际运算中还有一定的困难.
关于素数还有很多精彩的算法, 比如验证素数的 Miller-Rabin 测试, 以及应用素数性质的 RSA 加密算法, 但有关生成素数的真正可行的算法, 还有待我们继续去探究.
Read more…
去年就开始用 Mathematica 了, 在今年 Wolfram|Alpha 推出后, 我使用 Mathematica 的次数就越来越多了, 但有时候有的函数用起来还是不够得心应手, 所以前几天特意看了一下 Overview, 把初用者需要的重点记了下来, 难免会有不准确之处, 请各位大牛批评指正.
另外, 最近一直都很忙, 有几个话题一直没写完, 所以有段时间没有更新, 望各位见谅.
Read more…
有的时候我们需求一种简介的表示数的方法，对于普通的有理数来说，普通的分数足够了。但是对于无理数，普通的分数可就无能为力了。我们有没有简介的方法来表示无理数呢？
连分数( continued fractions )就是这样的一种表示数的方法，连分数是形如下图的式子。
我们一般将连分数简写成
Read more…
高斯消元法是一个解线性代数方程组的重要消元法，其重要作用是可以应用于计算机的解线性方程。应为通过它可以构造一个三角矩阵（又称行梯阵式），然后通过迭代的方法求解。
根据高斯消元法的理论，我们只需要n个系数非零的n元方程，即可求解这一方程组。
所以讨论一个n元的行梯阵式，我们只需要看前n行，即可求解。
高斯消元法把一个阵式构造成行梯阵式（三角矩阵）的过程是（只讨论n元矩阵的前n行）：设要求解的未知数分别为x1,x2,x3……xn，有R1……Rn个线性方程，线性方程Ri中xj的系数为aij，则用-(ai1/a11)R1加上Ri来消除Ri的x1项，其中i>1。接下来，同样地，用-(aij/ajj)Rj加上Ri来消除Ri的xj项，其中i>j，且Rj……Rn的x1……x(j-1)项应已被R1……R(j-1)消除。
太抽象了？我给出3*3矩阵的求行梯阵式的过程。
算出行梯阵式后，可以将Rn（即xn）代入R(n-1)求出x(n-1)，然后将xn,x(n-1)代入R(n-2)求x(n-2)，……，一直迭代到求出x1.
懂了吗？呵呵，我的数学研究方向已经从计算机偏向自然科学了。