10赞

判断一个数是质数最快的方法？为什么？

作者：mobiledu2502916313 | 来源：互联网 | 2023-03-19 05:58

不明白。为什么，望指教**n>3andnisodd.*intisPrime(intn){intk,upperBoundn2;

不明白。为什么，望指教
/**
n>=3 and n is odd.
*/
int isPrime(int n)
{
    int k, upperBound=n/2;

    for(k=3; k<=upperBound; k+=2)
    {
        upperBound=n/k;
        if(n%k==0)
            return 0;
    }

    return 1;
}

46 个解决方案

#1

哪里不明白啊？？？时间复杂度最小啊

#2

假设n=A*B 则只需要测试不大于min(A,B)的数就能找到n的一个因子,每次加2而不会漏掉因子二是因为假设
n=2*A(则经过有限次后k会到达A),能找到n的一个因子A,同样不会误判n为素数

#3

那句不明白？

#4

upperBound=n/k;
假设2~k都已经测试过不是n的因子,但n是合数,设n=A*B,则 B=n/A < n/k (K 因此如果n是合数,则它的一个因子一定落在[0 n/k]内

#5

素数表搜索应该比这个快。

#6

upperBound 应该是N^1/2(根号N)取整才比较节约时间吧？

#7

换言之，一个数N，你为了判断它是否为质数，就开始试除3、5、7...但是，如果当除以（N^1/2取整，记为m）这个数的时候还没有能够除尽，那么就没有继续下去的必要了。因为假设N存在一个比m大的因数k，那么N/k是小于m的，这跟上述条件（N除以3、5、7...m都不能除尽）产生了矛盾

#8

这也不是最快的啊！

#9

最快的不知道，但楼主的这个算法估计是最慢的

#10

素数测试，
如果只保证一个很高概率成立的话
有更快的办法。

#11

实际上 upperbound就固定成sqrt(n)就成了
这样就好理解了吧，这是判断素数最简单的办法了

#12

upssdss

#13

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。

最小的素数是2，他也是唯一的偶素数。最前面的素数依次排列为：2，3，5，7，11，13，17，...... 　　不是质数且大于1的正整数称为合数。　　质数表上的质数请见素数表。　　依据定义得公式：　　设A=n2+b=(n-x)(n+y),除n-x=1以外无正整数。故有：　　y=（b+nx)/(n-x) (x

#14

算术基本定理
　　算术基本定理：　　任何大于1的正整数n可以唯一表示成有限个素数的乘积: n=p_1p_2...p_s, 这里p_1≦p_2 ≦...≦p_s是素数。　　这一表达式也称为n的标准分解式。　　算术基本定理是初等数论中最基本的定理。由此定理，我们可以重新定义两个整数的最大公因子和最小公倍数等等概念。　　1不能称作素数，是因为要确保算术基本定理所要求的唯一性成立。这一解释可参看华罗庚《数论导引》
[编辑本段]素数分布问题
　　素数分布问题，就是指素数在正整数集或其特殊子集中的分布情况，比如素数个数问题等等。这方面的结果如下; 　　（1）欧几里得以反证法证明了素数个数无限；欧拉利用解析方法也证明了此结论。　　（2）高斯提出著名的素数定理（当时是猜想，后被证明）：设π(x)是不超过x的素数个数，那么极限(x趋向于无穷) 　　lim π(x)/(x/Ln x)=1 　　更好的逼近公式有高斯提出的li(x)函数，即lim π(x)/lix=1。　　其中　　（3）狄利克雷证明了任何等差数列： a, a+d,a+2d,...a+nd,... (这里a,d互质)中都包含无限个素数。　　（4）兰伯特猜想（已被证明）：在n和2n之间必定存在一个素数，这里n是大于1的正整数。　　

#15

呵呵，谭浩强的c语言里好像提到判断到根号n就可以了

#16

说快的话，LZ给的方法不算太快，当n很大的时候，效率比较低。
一般常用的是米勒-罗宾，log(n)^2应该可以搞定，前几年，印度的科学家给出了一种测试方法，
是确定的并且时间复杂度为常数，不过常数比较大，大概10^8左右，在实际应用当中，一般比不上米勒-罗宾。

#17

引用 16 楼 litaoye 的回复:

前几年，印度的科学家给出了一种测试方法，
是确定的并且时间复杂度为常数，不过常数比较大，大概10^8左右，在实际应用当中，一般比不上米勒-罗宾。

乃这个故意留给人吐槽的么……第一AKS那三个人A是教授KS两个都是本科生，科学家什么的……第二明显是多项式算法不是常数算法……

#18

确实是多项式时间的,大概在O(lg(n)^12)

#19

不好意思，复杂度是看别的文章里说的，自己没分析过。

btw，这个n是位数么？

引用 18 楼 fanster28_ 的回复:

确实是多项式时间的,大概在O(lg(n)^12)

#20

不算故意的，确实真的不知道，指正了就好。

引用 17 楼 fancymouse 的回复:

乃这个故意留给人吐槽的么……第一AKS那三个人A是教授KS两个都是本科生，科学家什么的……第二明显是多项式算法不是常数算法……

#21

讨论是否是多项式算法是依照输入数据的长度来算的。这里如果n是数值的话那log(n)才是长度。在log(n)上可以12次方做出来所以PRIMES is in P了咯

#22

这个是什么算法？

#23

Miller-rabbin算法比LZ的这个快多了

#24

楼主给的好像不对，4没有考虑到

#25

这。。。老帖被挖出来了

#26

试了一下：
isPrime(8)
返回1

有问题吧？

#27

6*N + 1
6*N + 5
特殊 2、3

#28

这样计算效率低

#29

貌似偶数都没排除。。
应该是楼主少添加了一个判断if(n&1)
如果是素性检验的话，miler那个只是以很高概率的保证是素数。信安数基没怎么好好看，老师讲解RSA的也没怎么听。

#30

http://www.cnblogs.com/skyivben/archive/2010/07/10/1775001.html

#31

该回复于2010-08-05 15:51:51被版主删除

#32

判断一个数是质数

最快的办法是：

查质数表！～～

#33

判断素数的最快算法……我也不知道，只知道两种比较快的，
一种是在根号N内的所有素数一一试除

还有一种是概率算法，用费马小定理的逆定理（当然不成立，所以只是概率算法）
满足a^(n-1) mod n=1 的合数是非常少的，听说用取a=2,3,5,7，11,13测试在maxlongint（pascal语言中最大长整形数）只有1个是合数

#34

算法可以参见百度百科“费马小定理”，时间复杂度也是很理想的，常数级。

#35

引用 33 楼 zyjpjl 的回复:

判断素数的最快算法……我也不知道，只知道两种比较快的，
一种是在根号N内的所有素数一一试除

还有一种是概率算法，用费马小定理的逆定理（当然不成立，所以只是概率算法）
满足a^(n-1) mod n=1 的合数是非常少的，听说用取a=2,3,5,7，11,13测试在maxlongint（pascal语言中最大长整形数）只有1个是合数

341,550,071,728,321最小反例，俺没看到过有什么报告称这是int64范围内唯一一个。由于这个数比起2^64来少了很多因此有理由相信在int64里还有至少几个反例。

#36

唔。引用错数字了。刚才那个是测试到17的时候的最小反例。只测试到13的话最小反例是3,474,749,660,383。比maxint32要大多了，比maxint64要小多了。

#37

你那是只测试一个数字，注意我指的是这几个数字都要测试……

#38

其实就是米勒罗宾，估计FancyMouse同志给出的这个数，应该是这几个都能测过的（2-17），否则用不着这么大，能通过测试的合数多了。不过具体怎么找到这么大的数的，就不清楚了。估计Int64范围的话，还得多测几个。

引用 37 楼 zyjpjl 的回复:

你那是只测试一个数字，注意我指的是这几个数字都要测试……

#39

引用 15 楼 minitoy 的回复:

呵呵，谭浩强的c语言里好像提到判断到根号n就可以了

那个方法不好理解效率还低

#40

其实这个问题很复杂

AR素性检查,比上面提到的方法都快,都缺点是不能给出其因子,若判断一个数是素数,该方法所能给出的全部信息就是:此数不是素数,仅此而已

#41

AR素数检测是什么？可否详细讲一下。

引用 40 楼 njwangchuan 的回复:

其实这个问题很复杂

AR素性检查,比上面提到的方法都快,都缺点是不能给出其因子,若判断一个数是素数,该方法所能给出的全部信息就是:此数不是素数,仅此而已

#42

我也不了解AR检测是什么，不过楼上的回复其实是有些不严谨的，比如不能给出其因子，如果是素数就不存在什么因子，另外这个检测相信也不是一个确定性的检测，大概跟Rabin-Miller类似，复杂度上也不可能低于log(n)。

引用 41 楼 zyjpjl 的回复:

AR素数检测是什么？可否详细讲一下。

#43

判断一个数是质数最快的方法？
for (k = 3; k <= upperBound; k += 2)
            {
                upperBound = n / k;
                 if (n % k == 0)                    return 0;
            }
换成 if(n%k!=0)
这样应该也行吧

#44

如果要计算合数的个数是必须要判断到根号n，直接到n就错了。像6，除了个2算1个，除了个3也算1个。

#45

引用 44 楼的回复:

如果要计算合数的个数是必须要判断到根号n，直接到n就错了。像6，除了个2算1个，除了个3也算1个。

楼主有没有考虑过根号n，人家是上取整呢。。。

#46

见到了很多个算法的名字……但是都没见到具体的算法步骤……

推荐阅读

io
用户在线广告点击行为预测的深度学习模型ctriptech

本文来自英国伦敦大学学院博士张伟楠在携程技术中心主办的深度学习Meetup中的主题演讲，介绍了深度学习在在Multi-fieldCategorical ... [详细]

蜡笔小新 2023-03-20 21:28:27
hash
使用GO语言实现POW挖矿

使用GO语言实现POW挖矿,Go语言社区,Golang程序员人脉社 ... [详细]

蜡笔小新 2023-03-20 21:23:36
int
AI医疗与人类疾病的竞跑：5G落地，就像“三甲”到家

　　人类与疾病缠斗的历程中，加载5G技术的人工智能(AI)将以前所未有的能量参与、引领变革。　　首先是辅助诊断的AI技术。“男，38岁，肺结节随访，可疑病灶6个：第1处右肺上叶、尖段，长径3.3× ... [详细]

蜡笔小新 2023-03-20 21:16:36
case
[数据结构]散列表（哈希表）

在这里没有新的原创性的东西。该部分内容主要取材于《软件设计师教程》部分的内容。我想强调一种数据结构，散列表。它是基于快速存取的角度设计的，也是一种典型的 ... [详细]

蜡笔小新 2023-03-20 20:23:03
case
网站关键词一般如何设置，网站关键词设置准则

关键词是SEO的核心任何的搜索必须都通过关键词来进行搜索跳转，那么你的网站如何设置关键词以被搜索引擎优先抓取并且给到更好的排名就成为关键性问题。那么网站关键词如何设置呢，怒蛙网络 ... [详细]

蜡笔小新 2023-03-20 23:27:05
case
线段树-离散化处理点

博客：http:www.cnblogs.comwuyiqiarchive201203192405885.htmlThecitizensofBytetow ... [详细]

蜡笔小新 2023-03-20 23:16:39
case
一切都可以玩起来！

易悦科技专注于020企业，重运营，垂直于互联网+大消费领域。是全球领先的互联网+大消费领域服务商。旗下拥有奔跑 ... [详细]

蜡笔小新 2023-03-20 23:05:34
int
#每日Linux小练习#04 find指令

今天对find指令进行练习原材料来源于http:www.cnblogs.comwanqieddyarchive201106092076785.htmlfindpath-option ... [详细]

蜡笔小新 2023-03-20 22:58:44
int
开发笔记:Sql Service的艺术 SQL多表查询

开发笔记:Sql Service的艺术 SQL多表查询 ... [详细]

蜡笔小新 2023-03-20 22:25:42
int
Adaboost算法的原理与推导——转载及修改完善

《Adaboost算法的原理与推导》一文为他人所写，原文链接： http:blog.csdn.netv_july_varticledetails40718799另外此文大部分是摘录 ... [详细]

蜡笔小新 2023-03-20 22:20:35
int
js 字符串转换为数值

js 字符串转换为数值 ... [详细]

蜡笔小新 2023-03-20 21:56:06
int
10.rabbion负载均衡和服务调用

springcloudribbon是基于NetflixRibbon实现的一套客户端(注意是客户端)负载均衡工具LB负载均衡(LoadBalance)是什么简单的说就是将用户的请求平 ... [详细]

蜡笔小新 2023-03-20 21:49:33
request
python关闭word_利用Python爬取翻译网站的翻译功能

现在我想分享一个利用Python技术，爬取一个翻译网站的翻译功能的小代码。首先隆重介绍我们今天将要爬取的网站：http:fy.iciba.com咱们用P ... [详细]

蜡笔小新 2023-03-20 21:44:40
window
mac android studio 模拟器启动不了,Mac os下android studio模拟器无法联网解决方法

SQLAlchemy几种查询方式总结转自:http:blog.csdn.netshudaqi2010articledetails51568219几种常见sqlalchemy查询:# ... [详细]

蜡笔小新 2023-03-20 21:34:20
request
为什么Owin.Hosting.StartOptions需要管理员权限？

如何解决《为什么Owin.Hosting.StartOptions需要管理员权限？》经验，应该怎么办？ ... [详细]

蜡笔小新 2023-03-20 21:19:06

mobiledu2502916313

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章