c语言找10000内的素数,程序设计找出1~10000内素数并排除伪素数

程序设计找出1~10000内素数并排除伪素数

答案:1  信息版本：手机版

解决时间 2019-10-03 07:58

已解决

2019-10-02 21:38

(1) 设计出时间和空间复杂性低的算法；

(2) 基于费马小定理，找出1——10000中的所有素数并且能排除伪素数。

设计提示：为了判定任意给定的正数n是否为素数，可利用费马小定理，对某个整数a (0嗯，用visual c++

全部回答

1楼

2019-10-02 22:34

名称解释 若n能整除2^(n-1)-1,并n是非偶数的合数，那么n就是伪素数。 伪素数的例子 2^(5-1)-1=15,15|5. 2^(3-1)-1=3,3|3.但很多都是素数，如3，5，7，29，31…… 1919年数学家萨鲁斯找到了反例：2^(341-1)-1|341,而341=11*31是合数，341就成了第一个伪素数。以后又发现了许多伪素数：561 645 1105 1387 1729…… 素数的起源与研究 能整除an一a的合数n，a≥2，(a，n)＝1，被称为以a为底的伪素数，简记为a-伪素数。 伪素数起源于17世纪法国数学家费马的某些研究。他于17世纪30年代末曾写信给法国数学家梅森，提到这样一个命题：2p一2能被素数p整除。后来，在他1640年10月18日给德贝西的信中说，他进一步证明了这样一个定理： 如果p是一个素数，且a不能被p整除，则ap-1－1能被p整除(等价的说法是ap－a能被素数p整除)。 后人称这个定理为费马小定理，以和费马大定理相区别。费马小定理奠定了现代数论中素数判定的基础。 按费马小定理，如果一个奇数n不能整除2n－2，则n必为合数(这是费马小定理的一个逆否命题)。但是，如果奇数n＞1能整除2n－2， n就一定是素数吗？就是说，费马小定理的逆命题是否成立？对于1＜n＜300的数来说，计算可知，能整除2n－2的奇数n都是素数，这使得人们在很长的时间内认为费马小定理的逆命题当然成立。德国数学家莱布尼茨曾在1680年6月和1681年12月两次宣布他证明了这样一个命题：如果n不是素数，则2n－2不能被n整除(这是下述命题的逆否命题：如果2n－2能被n整除，则n是素数)，但没发表他的证明。1742年4月，德国数学家哥德巴赫在给欧拉的信中表示要证明费马小定理的逆定理，但似乎也无结果。 1819年，法国数学家沙路斯发现，虽然341整除2341-2，但341是合数，341＝11×31。这一反例表明费马小定理的逆定理不成立。1830年，一位匿名德国数学家指出更一般的构造反例的方法，他指出，只要能找到两个奇素数p和q，使它们的积pq能同时整除2p-1-1与2q-1-1，那么就可得到pq整除2pq-1-1。按此方法，人们发现除341外，还有561，645，1105，1389，1729，1905等也具有上述性质。于是，人们把能整除2n一2的合数n称为伪素数。1926年，普列特制成5000万以内的伪素数表，1938年他又推进上限到1亿，为此，有时伪素数亦被称为普列特数。 提出伪素数后自然就产生了类似素数的问题，并得到人们的研究。如伪素数有多少个？人们指出，伪素数有无穷多，1903年麦洛用一个构造性方法对此加以证明。他证明了，若n是奇伪素数，那么，n = 2n-1－1也是奇伪素数，我们已知有奇伪素数n0＝341，按此法就可以构造出无穷多的奇伪素数来。再如是否存在偶伪素数?1950年，美国数学家d．h．莱默尔找到了第一个偶伪素数161038，161038＝2×73×1103，73 |(2161038-2)，1103 |(216038-2) 。1951年，荷兰的毕格尔又找到了一个偶伪素数，并证明了存在无穷多个偶伪素数。 后来人们针对费马小定理的一般情况，把伪素数概念一般化，就得出前面的定义。1904年，意大利数学家奇波拉给出一种构造a-伪素数的方法： 对于已知的整数a≥2，取p是任一奇素数，使p不能整除a(a2一1)，则n=(a2p-1)/(a2-1)是a-伪素数。 他同时也证明了存在无穷多的一般伪素数。当然，在一般伪素数研究中，也有许多未解决的问题。例如，1952年杜帕克提出的，能否存在无穷多个伪素数，它们同时以2和3为底，或更一般些，能否存在无穷多个伪素数，它们同时以两个不同的整数a与b为底(a≥2，b≥2，且a与b不是同一个整数的幂)。 伪素数的一个用途是利用伪素数表来判定一个奇数n是否为素数，这是d．h．莱默尔提出来的：如果n不能整除2n-1－1，则据费马小定理知，n必为合数；如果n能整除2n-1－1，且n在伪素数表中，则n为合数，否则为素数。这种方法的关键就在于按伪素数表去掉伪素数，而这要求伪素数在能整除2n-1－1的数中相当少才行，这就是当n整除2n-1-1时，n是合数的比例问题。在前10亿个自然数中，共有50847534个素数，而只有以2为底的伪素数5597个，即在此范围内n整除2n-1－1产生合数的可能性只有0.011%。所以人们把整除2n-1-1的正整数n(＞1)称为殆素数。在10亿之内，n整除2n-1－1同时整除3n-1－1的合数n只有1272个，即此时产生合数的可能性只有0.0025%。 如果存在合数n，对任何a＞1，只要(a，n)＝1时，n能整除an-1-1，则n被称为卡迈克尔数。这种数是由美国数学家r．d．卡迈克尔于1912年提出来的。最小的卡迈克尔数为561，这种数在自然数中更少了，在10亿之内，只有646个。一个问题就是：卡迈克尔数是否有无穷多？

我要举报

如果感觉以上信息为低俗/不良/侵权的信息，可以点下面链接进行举报，我们会做出相应处理，感谢你的支持！

大家都在看

推荐资讯