找到一个数是素数，为什么检查直到n / 2更好。在n的后半部分避免麻木的原因是什么 [英] To find a number is prime, Why checking till n/2 is better. What is the reason for avoiding numbres in second half of n

问题描述

要检查数字是否为质数，幼稚的方法是尝试将数字除以2到n，如果任何运算的余数为0，那么我们说给定的数字不是质数。
但最好只划分和检查直到n / 2（我知道更好的方法是直到sqrt（n）），我想知道跳过下半部分的原因。

To check if a number is prime or not, the naive way is to try dividing the number by 2 thru n, and if any operation gets remainder as 0, then we say the given number is not prime. But its optimal to divide and check only till n/2 (am aware much better way is till sqrt(n) ), I want to know the reason for skipping the second half.

假设是否需要检查数字11是否为质数，
11/2 =5。如果我们执行11/6或11/7或11/8或11，则
/ 9或11/10，在这两种情况下，我们都不为0。
对于任何给定的数字n都是如此。

say if we need to check number 11 is prime or not, 11/2 = 5. if we do 11/6 or 11/7 or 11/8 or 11/9 or 11/10 in neither of these cases we get remainder as 0. So is the case for any given number n.

避免下半年？ 如果将给定数字除以大于给定数字一半的任何数字，则余数永远不会为0，换句话说，大于给定数字一半的数字都不能除以给定数字

Is the reason for avoiding second half this? "if you divide the given number by any number which is more than given number's half, remainder will never be 0 Or in other words, none of the numbers which are more than the given number's half can divide the given number"

请帮助我知道是否正确

推荐答案

因为，最小的倍数会不能使它的质数为2。如果检查了从0到n / 2的所有数字，可能剩下多少倍呢？如果2的倍数大于n，则3或4的倍数也将大于n。

Because, the smallest multiple that will not make it a prime is 2. If you have checked all the numbers from 0 to n/2, what multiple is left that could possibly work? If multiple by 2 is bigger than n, then a multiple of 3 or 4 etc will also be bigger than n.

因此，任何数字N的最大因数必须< ; = N / 2

So the largest factor for any number N must be <= N/2

是的，取N / 2，并检查所有小于或等于N / 2的整数。因此，对于11，您将检查所有小于5.5的整数，即1、2、3、4和5。

So yes take N/2, and check all integers smaller or equal to N/2. So for 11 you would check all integers smaller than 5.5, i.e. 1, 2, 3, 4 and 5.

此处说明了平方根：
< href = https://stackoverflow.com/questions/5811151/why-do-we-check-upto-the-square-root-of-a-prime-number-to-determine-if-it-is- pri>为什么我们要检查素数的平方根来确定它是否为素数？

而这个问题以前曾被问过。

And this question has been asked before.

这篇关于找到一个数是素数，为什么检查直到n / 2更好。在n的后半部分避免麻木的原因是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！