在求3到100之间的素数的c语言题中，有一步是要开平方，是为什么?
2个回答
展开全部
这是为了提高效率，减少判断次数。
按定义，要判定数n是一个素数，要确定n不能被2~n-1整除。事实上，若n能被2~n-1中的某个整数k整除，则它必定能被整数(n/k)整除。如果k与(n/k)不相等，则其中必有一个小于√n；
如果k与(n/k)相等，则必有k=√n。
所以只要检查2~√n，就可确定n是否素数。这可以大大提高效率，举例，要判定1000003是素数，照前面的算法，要作1000001次除法才能下判断；而用后一种算法，只要作999次除尘即可下判断。效率提高1001倍。
按定义，要判定数n是一个素数，要确定n不能被2~n-1整除。事实上，若n能被2~n-1中的某个整数k整除，则它必定能被整数(n/k)整除。如果k与(n/k)不相等，则其中必有一个小于√n；
如果k与(n/k)相等，则必有k=√n。
所以只要检查2~√n，就可确定n是否素数。这可以大大提高效率，举例，要判定1000003是素数，照前面的算法，要作1000001次除法才能下判断；而用后一种算法，只要作999次除尘即可下判断。效率提高1001倍。
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
