找到一个素数？ [英] Find a prime number?

问题描述

要找到N是否是质数，我们只需要寻找小于或等于开方（N）的所有数字。这是为什么？我写一个C code所以想了解它背后的原因。

To find whether N is a prime number we only need to look for all numbers less or equal to sqrt(N). Why is that? I am writing a C code so trying to understand a reason behind it.

推荐答案

N是素数，如果它是一个正整数由正好两个正整数，1和除尽N。由于许多的除数不能大于该数时，这产生了一个简单的素性测试

N is prime if it is a positive integer which is divisible by exactly two positive integers, 1 and N. Since a number's divisors cannot be larger than that number, this gives rise to a simple primality test:

• 如果一个整数N，大于1，是不是在范围内的任意整数整除 [2，N-1] ，则N是一个素数。否则，N不是素数。

• If an integer N, greater than 1, is not divisible by any integer in the range [2, N-1], then N is prime. Otherwise, N is not prime.

不过，这将是很好的修改此测试，使其更快。因此，让我们展开调查。

However, it would be nice to modify this test to make it faster. So let us investigate.

需要注意的是N的约数是成对出现的。如果N是由一个数M除尽，那么它也由N / M整除。例如，12是6 divisble，因此也被2.此外，如果 M＆GT; =开方（N），那么 N / M ＆LT; =开方（N）

Note that the divisors of N occur in pairs. If N is divisible by a number M, then it is also divisible by N/M. For instance, 12 is divisble by 6, and so also by 2. Furthermore, if M >= sqrt(N), then N/M <= sqrt(N).

这意味着，如果不小于或等于开方（N）分频N个数字，比开方更大的无数字（N）整除n或者（除1和N本身），否则，矛盾就会出现。

This means that if no numbers less than or equal to sqrt(N) divide N, no numbers greater than sqrt(N) divide N either (excepting 1 and N themselves), otherwise a contradiction would arise.

因此​​，我们有一个更好的测试：

So we have a better test:

• 如果一个整数N，大于1，是不是在范围任意整数整除[2，开方（N）] ，则N是一个素数。否则，N不是素数。

• If an integer N, greater than 1, is not divisible by any integer in the range [2, sqrt(N)], then N is prime. Otherwise, N is not prime.

如果你认为上面的理由，你应该看到的是，一些它通过测试也通过第一次测试，以及一些它未能做到这一点也失败了第一次测试。测试因此等价的。

if you consider the reasoning above, you should see that a number which passes this test also passes the first test, and a number which fails this test also fails the first test. The tests are therefore equivalent.

这篇关于找到一个素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！