龙空技术网

古希腊数学家埃拉托斯色尼教我们如何筛选质数的方法

春风拂柳夕阳斜 117

前言:

现时我们对“筛选法求素数流程图”大体比较关怀,我们都需要分析一些“筛选法求素数流程图”的相关内容。那么小编同时在网上网罗了一些关于“筛选法求素数流程图””的相关内容,希望看官们能喜欢,朋友们一起来了解一下吧!

在2200年前,古希腊亚历山大城市里,生活着一个知识渊博的学者,在他年迈后双眼失明,再也无法进行学习和研究,他觉得失去了生命存在的意义,绝食而死。

这不是一个虚构的故事,而是真实地在历史上存在着。编者,一个碌碌无为的咸鱼,看到这个数学家的故事时,久久无语。

这个老人就是我要介绍的数学家——埃拉托色尼。

埃拉托色尼,Eratothenes,出生于公元前275,出生于古希腊昔兰尼(今利比亚),是一位伟大的数学家,哲学家,天文学家和地理学家,曾经做过亚历山大里亚图书馆馆长,据说和阿基米德私交不错。

亚历山大里亚图书馆是当时西方世界最高的科学和知识中心,能担任馆长的都是德高望重,众望所归的学者。

他的主要成就在天文学和地理学,被西方地理学家称呼为“地理学之父”,因为他第一次创造了“地理学”这个词汇,替代“地方志”这个传统说法。他的著作有《地球大小的修正》和《地理学概论》,可惜都失传了,后世人只能通过其他作者的引文来了解。

他是历史上第一次测量地球的周长,大概4万公里,和实际周长4.0076万公里相差无几,他还计算出太阳和地球之间的距离1.47亿公里,和实际的距离1.49亿公里也很接近。(打字的时候,编者都不敢相信这是真的)

既然要介绍的是数学家,下面就说说他在数学上的成就。

现在有一个以他名字命名的筛选素数的方法,埃拉托色尼筛选法,简称埃氏筛或爱氏筛。

素数,需要介绍吗?素数还有个称呼就是质数。小学5年级学习的知识。

埃拉托斯色尼筛选法:要想得到一个自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,其他剩余的都是。

举数字100做例子。

第一步:100开平方根得到10,

第二步:求1~10之间的素数有2,3,5,7,

第三步:从1~100·把2,3,5,7的倍数地数去掉,

剩余的其他数都是素数。

我用颜色标了图,把2选定为素数颜色红色,再把2的倍数标为绿,去掉,再去掉3的倍数蓝色,5的倍数黄色,7的倍数紫色,剩下的就是素数,我全部涂成红色了。

同样的,我们可以算1万的素数,第一步1万开平方根等于100,然后得出100以内的素数25个,然后去除这25个素数的所有倍数,就得到1万以内所有的素数了。计算机跑起来很快的。

同样的,计算1亿以内的素数,那就1亿开平方,得到1万,计算1万以内的所有素数,再从1亿个数里把这些素数的倍数全部去除掉就可以了。算1万以内的素数,就是求1万的开方……这个过程上面写了,不赘述了。

这个方法还有另外一个用途,常常应用在判断一个数是不是素。

例如:967是不是质数呢?

那我们先把967开平方,约为31.1,那我们可以找31以内的素数,那就是2,3,5,7,11,13,19,23,29,31。问题就变成判断967是不是这几个数的倍数,而不用思考其他的。

这个方法第三个用途,可以应用在因式分解上,判断一个数是合数后,很容易知道他是哪几个素数的倍数。

这个和欧几里德的碾转相除法求最大公约数,都是极其具有实用价值的方法。

大家可以动动脑筋想想,还有没有其他的用途?

科普数学·一个数学家一个公式·泰勒斯·泰勒斯定理 科普数学·一个数学家一本书·欧几里德·几何原本 科普数学家:阿基米德 发现黄金比例,解决历史上第一次数学危机的古希腊数学家欧多克斯 科普数学·一个数学家一个公式·毕达哥拉斯·勾股定理 期末考完神兽写的科普我国数学家——祖冲之 占星大师,天文学大师,绘图专家,托勒密最爱数学家的头衔 科普数学家之阿波罗尼奥斯之《圆锥曲线论》 古希腊数学家丢番图墓志铭,传世之作《算术》,让我们学的头疼 曾被亚里士多德批评的数学家,被世界误解两千多年,直到量子论的 比哥白尼早1800年提出日心说的数学家是谁?阿里斯塔克

标签: #筛选法求素数流程图 #筛选法判断素数 #筛选法判断素数的依据 #用筛选法求某自然数范围内的全部素数 #判断素数为什么要开根号