社区
Java SE 帖子详情 问一个超级弱的问题，求素数中为什么要先开平方 ldhscxl 2009-03-21 05:50:47 这是算法上的问题，好好考虑一下算法，还要考虑一下素数的定义。
素数是只有1和本身能整除的整数。所以在求素数的时候，要将素数与1到素数本身中间的所有整数都相除，看是否有整除的数，如果有，那肯定不是素数了。但是从算法上考虑，为了减少重复量，开平方后面的数就不用相除了，因为a/b（平方数）=c（小一点的数），同样a/c=b。举例说明：
25，开平方以后是5,那么整除2~5就可以了，如果有满足条件的，就是素数。
看完之后还是晕，谁能解释的再清楚一些
...全文
1361 20 打赏 收藏 问一个超级弱的问题，求素数中为什么要先开平方 这是算法上的问题，好好考虑一下算法，还要考虑一下素数的定义。 素数是只有1和本身能整除的整数。所以在求素数的时候，要将素数与1到素数本身中间的所有整数都相除，看是否有整除的数，如果有，那肯定不是素数了。但是从算法上考虑，为了减少重复量，开平方后面的数就不用相除了，因为a/b（平方数）=c（小一点的数），同样a/c=b。举例说明： 25，开平方以后是5,那么整除2~5就可以了，如果有满足条件的，就是素数。 看完之后还是晕，谁能解释的再清楚一些 复制链接
扫一扫 分享 转发到动态 举报 AI 作业
写回复 配置赞助广告取 消
确 定
用AI写文章 20 条回复 切换为时间正序 请发表友善的回复… 发表回复 打赏红包 需支付: 0.00 元 取 消 确 定 ADemon_T 2009-03-23 打赏举报 回复 素数从2开始算的。。1不是素数。。。 wclszh 2009-03-23 打赏举报 回复 顶，学习 chumignze 2009-03-23 打赏举报 回复 节省运算效率 v先生在成都 2009-03-23 打赏举报 回复 这个问题不弱，谢谢 wangsuwen 2009-03-23 打赏举报 回复 学习了 Wbl314 2009-03-22 打赏举报 回复 目的 是为了减少循环次数，提高效率
原因： 一楼正解 jiest1986 2009-03-22 打赏举报 回复 请先学数学 tosshl 2009-03-22 打赏举报 回复 a=(a^1/2)*(a^1/2)
如果a不是素数
那么a有一个因子b a=b*c;
那么a的因子中（b或c）必定有一个是小于等于a^1/2的
所以判断的时候不用判断到1-a，只需要1-a^1/2 yang677888 2009-03-22 打赏举报 回复 这是输入一个数，判断有多少个素数
#include
using namespace std;
bool IsPrime( int n )
{
int bf = int( floor( sqrt(n) ) );
for( int i = 2; i <= bf; i++ )
{
if( n%i == 0 )
{
return false;
}
}
return true;
}
int main()
{
int n, amount;
amount = 0;
cout << "Please input a number:";
cin >> n;
unsigned int uiStart, uiStop;
uiStart = GetTickCount();
for( int i = 2; i < n; i++ )
{
if( IsPrime(i) )
{
amount++;
//cout << i << " ";
}
}
cout << endl << "There is/are " << amount
<< " Prime Numbers between 1 and " << n << endl;
return 0;
} yang677888 2009-03-22 打赏举报 回复 开方是为了减少除数的量，这样大大提高除数求余效率。开平方后面的数就不用相除了，因为开方得的数是除数最大因子了。 如81开方得9，9是除数最大因子，除数9后面的数就不用除了。
这是一个简单判断素数列子：（C语言主要代码）
bool IsPrime( int p )
{
for( int i = 2; i < p; i++ )
{
if( p%i == 0 )
return false;
}
return true;
}
要开方判断素数（C语言主要代码）
bool IsPrime( int p )
{
int bf = int( floor( sqrt( double(p) ) ) );
for( int i = 2; i <= bf; i++ )
{
if( p%i == 0 )
return false;
}
return true;
}
chjmars31728 2009-03-22 打赏举报 回复 同意一楼的说法 ZiSheng 2009-03-22 打赏举报 回复 确实很严禁 爱摸鱼de老邪 2009-03-22 打赏举报 回复 [Quote=引用 2 楼 banhcenzhaij 的回复:]
定义a=x*y (a,x,y都是正整数)
如果x和y都大于a的开平方
那么x*y>a,矛盾了.
所以必有一个数是小于等于a的开平方,如果这个数不等于1,那么a就是素数了.
[/Quote]
顶2楼，这个讲法很严谨很科学。 __浮夸 2009-03-22 打赏举报 回复 [Quote=引用 2 楼 banhcenzhaij 的回复:]
定义a=x*y (a,x,y都是正整数)
如果x和y都大于a的开平方
那么x*y>a,矛盾了.
所以必有一个数是小于等于a的开平方,如果这个数不等于1,那么a就是素数了.
[/Quote]
将的很仔细了 EvilCross 2009-03-22 打赏举报 回复 1楼说的很好， orangemike 2009-03-21 打赏举报 回复 利用数学概念降低搜索范围.
如果真的存在a*b = n,其中b大于n^(1/2)那么必然有a小于n^(1/2). cheng_fengming 2009-03-21 打赏举报 回复 同意一楼说的 其实求素数完全可以根据素数的定义来判断
但是为了提高效率 对其开平方就可以了！ banhcenzhaij 2009-03-21 打赏举报 回复 定义a=x*y (a,x,y都是正整数)
如果x和y都大于a的开平方
那么x*y>a,矛盾了.
所以必有一个数是小于等于a的开平方,如果这个数不等于1,那么a就是素数了. ace62 2009-03-21 打赏举报 回复 比如，24的因数有1、2、3、4、6、8、12、24
按定义应该用2－23去除，但经过分析上面的数可以发现
1×24、2×12、3×8、4×6
如果2、3、4是某个数的因数，那么另外几个数也是，反之也一样
所以为提高效率，可以只检查小于该数平方根的那些数，如24的平方根大于4小于5，检查2－4就可
不知说清楚了没有，呵呵 yolov和deepsort的c语言实现_A c++ implementation of yolov5 and deep yolov和deepsort的c语言实现_A c++ implementation of yolov5 and deepsort.zip 2025年数据增强强度控制-基础卷（含答案及解析）.docx 2025年数据增强强度控制-基础卷（含答案及解析）.docx grpc-util-1.71.0.jar中文-英文对照文档.zip 1、压缩文件中包含：
中文-英文对照文档、jar包下载地址、Maven依赖、Gradle依赖、源代码下载地址。
2、使用方法：
解压最外层zip，再解压其中的zip包，双击 【index.html】 文件，即可用浏览器打开、进行查看。
3、特殊说明：
（1）本文档为人性化翻译，精心制作，请放心使用；
（2）只翻译了该翻译的内容，如：注释、说明、描述、用法讲解 等；
（3）不该翻译的内容保持原样，如：类名、方法名、包名、类型、关键字、代码 等。
4、温馨提示：
（1）为了防止解压后路径太长导致浏览器无法打开，推荐在解压时选择“解压到当前文件夹”（放心，自带文件夹，文件不会散落一地）；
（2）有时，一套Java组件会有多个jar，所以在下载前，请仔细阅读本篇描述，以确保这就是你需要的文件。
5、本文件关键字：
jar中文-英文对照文档.zip,java,jar包,Maven,第三方jar包,组件,开源组件,第三方组件,Gradle,中文API文档,手册,开发手册,使用手册,参考手册。 2025年数据隐私保护匿名化技术-基础卷（含答案及解析）.docx 2025年数据隐私保护匿名化技术-基础卷（含答案及解析）.docx junit-platform-launcher-1.11.3.jar中文-英文对照文档.zip 1、压缩文件中包含：
中文-英文对照文档、jar包下载地址、Maven依赖、Gradle依赖、源代码下载地址。
2、使用方法：
解压最外层zip，再解压其中的zip包，双击 【index.html】 文件，即可用浏览器打开、进行查看。
3、特殊说明：
（1）本文档为人性化翻译，精心制作，请放心使用；
（2）只翻译了该翻译的内容，如：注释、说明、描述、用法讲解 等；
（3）不该翻译的内容保持原样，如：类名、方法名、包名、类型、关键字、代码 等。
4、温馨提示：
（1）为了防止解压后路径太长导致浏览器无法打开，推荐在解压时选择“解压到当前文件夹”（放心，自带文件夹，文件不会散落一地）；
（2）有时，一套Java组件会有多个jar，所以在下载前，请仔细阅读本篇描述，以确保这就是你需要的文件。
5、本文件关键字：
jar中文-英文对照文档.zip,java,jar包,Maven,第三方jar包,组件,开源组件,第三方组件,Gradle,中文API文档,手册,开发手册,使用手册,参考手册。
Java SE
62,631
社区成员
307,264
社区内容
发帖 与我相关 我的任务 Java SE Java 2 Standard Edition 复制链接
扫一扫 分享 确定 社区描述 Java 2 Standard Edition 社区管理员
加入社区
获取链接或二维码
近7日
近30日
至今
加载中
查看更多榜单
社区公告
暂无公告 试试用AI创作助手写篇文章吧
+ 用AI写文章