Sieve of Eratosthenes算法的代码

In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is a simple, ancient algorithm for finding all prime numbers up to a specified integer.[1] It works efficiently for the smaller primes (below 10 million).[2] It was created by Eratosthenes, an ancient Greek mathematician. However, none of his mathematical works survived—the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. [素数的定义是,一个仅能被1和本身整除的自然数]

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

[可以通过以下的埃拉托色尼筛选法寻求所有小于整数n的素数]

Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).

[列出从2到n的一串连续自然数]

Initially, let p equal 2, the first prime number.

[开始,先把2当作第一个素数,并赋值给变量p]

Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)

[将该列自然数中划掉p的倍数]

Find the first number remaining on the list after p (this number is the next prime); replace p with this number.

[将剩下的自然数按原来顺序重新组成新的一列,并将第一个数赋给变量p]

Repeat steps 3 and 4 until p2 is greater than n.

[重复第三第四步,直到p的平方大于n]

All the remaining numbers in the list are prime.

[剩下的自然数就是所有小于n的素数]

import math

limit=1000000000

L=[True]*limit

def seive(x):

    for i in xrange(x*2,limit,x):

        L[i]=False map(seive,[2])

map(seive,xrange(3,int(math.ceil(math.sqrt(limit))),2))

primer=[]

for i in xrange(2,limit):

    if L[i]: primer.append(i)

print primer

阅读全文 »

CentOS 5升级python版本(2.4>2.7)

日前在CentOS上搭建测试环境时候,遇到需要升级python版本的情况,于是就记录了整个升级的过程:

     在CentOS5中自带的Python版本是2.4,但是目前许多基于Python的应用软件要求的Python版本应要高于2.4。升级python版 本的时候千万不能卸载python 2.4,再安装python2.7,这样会有无穷无尽的麻烦,保守的方式是直接安装python2.7的源码包,也就是python两个版本共存。(因为 Centos里面有很多程序是依赖着python,所有最好不要尝试去卸载python2.4)。

(1)下载/安装python

下载Python2.7.2.tar.bz2(http://www.python.org/ftp/python/2.7.2/Python- 2.7.2.tar.bz2)

$tar jxvf Python2.7.2.tar.bz2 $cd Python2.7.2

$./configure $make && make install 自此,python2.7安装后路径默认是在/usr/local/lib/python2.7 查看Python版本: $ /usr/local/bin/python2.7 -V

(2)建立软连接,使系统默认的python指向python2.7

正常情况下即使python2.7安装成功后,系统默认指向的python仍然是2.4版本,考虑到yum是基于python2.4才能正常工作,不敢轻 易卸载。如何实现将系统默认的python指向到2.7版本呢?

mv /usr/bin/python /usr/bin/python.bak (或者rm -rf /usr/bin/python)

ln -s /usr/local/bin/python2.7 /usr/bin/python

检验python指向是否成功 python -V

(3) 解决系统python软链接指向python2.7版本后,yum不能正常工作 方法:

$vi /usr/bin/yum 将文本编辑显示的#/usr/bin/python修改为#/usr/bin/python2.4,保存修改即可

阅读全文 »

linux命令手册-----rm(remove)

rm(remove)

功能说明:

删除文件或目录

语法 :

rm[-dfirv][--help][--version][文件或目录...]

包名称 :

coreutils

相关命令:

mdel

补充说明:

执行rm命令可删除文件或目录,如要删除目录,必须加上“-r”参数

参数 说明:

  • -d或--directory 直接把欲删除的目录的硬链接数目删成0,移除该目录
  • -f或--force 强制删除文件或目录。本参数将会忽略放在它前面的“-i”参数
  • -i或--interactive 删除已有文件或目录之前先询问
  • -r、-R或--recursive 递归处理,将指定目录下的所有文件及子目录一并处理
  • -v或--verbose 显示命令执行过程
  • --help 帮助
  • --version 版本信息

命令实例:

使用mkdir [root@localhost /]# mkdir test [root@localhost /]# rm -r test rm:是否删除 目录 “test”? y

阅读全文 »

linux命令手册----CP(copy)

cp(copy)
功能说明
复制文件或目录
语法
cp[-abdfilprRsuvx][-S<备份字尾字符串>][--help][--sparse=<使用时机>][--version][来源文件或目录][目的文件或目录]或cp[-abdfilprRsuvx][-S<备份字尾字符串>][--help][--sparse=<使用时机>][--version][来源文件或目录...][目的目录]

所属软件包
coreutils

相关命令
mcopy

相关信息
cp命令用来复制文件或目录,假如同时指定两个或两个以上的文件或目录,且最后的目的目录是一个已经存在的目录,则它会把前面指定的所有文件或目录复制到该目录中。若同时指定多个文件或目录,而最后的目的地不是一个已经存在的目录,则会出现错误信息。


参数
说明
-a或--archive
此参数的效果和同时指定“-dpR”参数相同
-b或--backup
删除、覆盖目的文件之前先备份,备份的文件会在字尾加上一个备份字符串
-d或--no-dereference
复制符号链接时,把目的文件或目录建立为符号链接,并指向源文件或目录连接的源文件或源目录。假如不加上这个参数,在复制过程中若遇到符号链接,则会直接复制该连接所指向的源文件或源目录,而不是重新建立一个指向该原始文件或目录的符号链接
-f或--force
强行复制文件或目录,不论目的文件目录是否已经存在
-i或--interactive
覆盖原有文件之前先询问
-l或--link
对来源文件建立硬链接,而非复制文件
-p或--preserve
保留源文件或目录的属性,包括所有者、所属组、权限和时间
-r
递归处理,将指定目录下的文件与子目录一并处理。若来源文件或源目录的类型,不属于目录或符号链接,则一律视为普通文件处理
-R或--recursive
递归处理,将指定目录下的所有文件及子目录一并处理
-s或--symbolic-link
对来源文件建立符号链接,而非复制文件
-S<备份字尾字符串>或--suffix=<备份字尾字符串>
用“-b”参数备份目的文件后,备份文件的字尾会加上一个备份字符串
默认的备份字尾字符串是符号~,可通过“-S”参数来改变它
-u或--update
使用这项参数之后,只会在来源文件的建立时间(Modification Time)晚于目的文件的时候,或是同名称的目的文件不存在时,才开始复制文件
-v或--verbose
显示命令执行过程
-x或--one-file-system
复制文件或目录存放的文件系统,必须与cp命令执行时所处的文件系统相同,否则复制进程不启动。即不处理在其他分区的文件
--help
帮助
--sparse=<使用时机>
设置存储稀疏文件(Sparse File)的时间。稀疏文件是一种内含大量连续0字节的文件,这种现象称之为空洞(Holes),许多的二进制文件都具有这种特性,假使文件系统有支持这种特性,这些空洞将不会占用大量的存储块,则对节省存放空间和提高系统性能都有益处。使用时机设为“auto”,则来源文件若是稀疏文件,目的文件也会是稀疏文件,这是cp命令的默认值,使用时机设为“always”,则目的文件将一概存储成稀疏文件。使用时机设为“never”,则目的文件将不会存储成稀疏文件
--version
版本信息
命令实例:
1)复制一个名字是file1的文件到另外一个目录下
[root@localhost /]# cp file1 newdir
 2)复制一个文件从目录/home/public/的文件test.txt复制到目录/home/public/backup/的文件test.bak
[root@localhost /]#cp /home/public/test.txt /home/public/backup/test.bak
3)使用通配符复制文件
[root@localhost /]#cp *.txt newdir

阅读全文 »

Project Euler 13解题报告

题目: Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. 37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28112879812849979408065481931592621691275889832738 44274228917432520321923589422876796487670272189318 47451445736001306439091167216856844588711603153276 70386486105843025439939619828917593665686757934951 62176457141856560629502157223196586755079324193331 64906352462741904929101432445813822663347944758178 92575867718337217661963751590579239728245598838407 58203565325359399008402633568948830189458628227828 80181199384826282014278194139940567587151170094390 35398664372827112653829987240784473053190104293586 86515506006295864861532075273371959191420517255829 71693888707715466499115593487603532921714970056938 54370070576826684624621495650076471787294438377604 53282654108756828443191190634694037855217779295145 36123272525000296071075082563815656710885258350721 45876576172410976447339110607218265236877223636045 17423706905851860660448207621209813287860733969412 81142660418086830619328460811191061556940512689692 51934325451728388641918047049293215058642563049483 62467221648435076201727918039944693004732956340691 15732444386908125794514089057706229429197107928209 55037687525678773091862540744969844508330393682126 18336384825330154686196124348767681297534375946515 80386287592878490201521685554828717201219257766954 78182833757993103614740356856449095527097864797581 16726320100436897842553539920931837441497806860984 48403098129077791799088218795327364475675590848030 87086987551392711854517078544161852424320693150332 59959406895756536782107074926966537676326235447210 69793950679652694742597709739166693763042633987085 41052684708299085211399427365734116182760315001271 65378607361501080857009149939512557028198746004375 35829035317434717326932123578154982629742552737307 94953759765105305946966067683156574377167401875275 88902802571733229619176668713819931811048770190271 25267680276078003013678680992525463401061632866526 36270218540497705585629946580636237993140746255962 24074486908231174977792365466257246923322810917141 91430288197103288597806669760892938638285025333403 34413065578016127815921815005561868836468420090470 23053081172816430487623791969842487255036638784583 11487696932154902810424020138335124462181441773470 63783299490636259666498587618221225225512486764533 67720186971698544312419572409913959008952310058822 95548255300263520781532296796249481641953868218774 76085327132285723110424803456124867697064507995236 37774242535411291684276865538926205024910326572967 23701913275725675285653248258265463092207058596522 29798860272258331913126375147341994889534765745501 18495701454879288984856827726077713721403798879715 38298203783031473527721580348144513491373226651381 ...

阅读全文 »

Project Euler 12解题报告

题目: The sequence of triangle numbers is generated by adding the natural numbers. So the 7 th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Let us list the factors of the first seven triangle numbers: 1 : 1 3 : 1,3 6 : 1,2,3,6 10 : 1,2,5,10 15 : 1,3,5,15 21 : 1,3,7,21 28 : 1,2,4,7,14,28 We can see that 28 is the first triangle number to have over five divisors. What is the value of the first triangle number to have over five hundred divisors? 中文题目: 三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 那么三角形数序列中的前十个是: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... 下面我们列出前七个三角形数的约数: 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 可以看出28是第一个拥有超过5个约数的三角形数。 那么第一个拥有超过500个约数的三角形数是多少? 解题报告: m = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279] n = 10000 li = [] while True: x = (n+1)*n/2 for i in m: t = 0 if x i: break if x % i != 0: continue while x % i == 0: x /= i t += 1 li.append(t) s = 1 for j in li: s *= (j+1) if s = 500: print (n+1)*n/2 break else: n += 1 li = [] ...

阅读全文 »

linux命令apt-get参数以及用法详解

apt-get作用: 用于自动从互联网的 软 件 仓库中搜索、安装、升级、 卸 载 软件或操作系统。 apt-get语法: apt-get [参数] apt-get参数: apt-get update 在修改 /etc/apt/sources.list或/etc/apt/preferences 之後运行该命令。此外您需要定期运行这一命令以确保您的 软件包 列表是最新的。 apt-get install packagename 安装一个新软件包(参见下文的 aptitude ) apt-get remove packagename 卸载一个已安装的软件包(保留配置文档) apt-get --purge remove packagename 卸载一个已安装的软件包(删除配置文档) apt-get autoclean apt会把已装或已卸的软件都备份在硬盘上,所以假如需要空间的话,能够让这个命令来删除您已删掉的软件 apt-get clean 这个命令会把安装的软件的备份也删除,但是这样不会影响软件的使用。 apt-get upgrade 更新任何已安装的软件包 apt-get dist-upgrade 将系统升级到新版本 ...

阅读全文 »

linux命令patch参数以及用法详解

 

patch作用:

补丁更新

patch语法:

gpm [参数][文件名]

patch参数:

-b 产生备份文件

-c 使用文本文件解释patch文件的用途

-d 目录 在做任何动作前先切换目录

-e 将结果翻译成批处理文件后输出

-f 不询问任何问题,强制运行

-i 修补文件 指定修补文件的位置

-l 忽略Tab和空格符

-s 安静模式,不显示错误信息

-v 显示版本信息

--binary 使用二进制模式来读写文件

--help 显示帮助文件

--dry--run 模拟并列出运行的结果,而不真的运行

 

patch示例:

patch file file.patch

阅读全文 »