[algorithm] 소수의 제곱근을 검사하여 소수인지 확인하는 이유는 무엇입니까?

숫자가 소수인지 여부를 테스트하려면 왜 그 숫자의 제곱근까지만 나눌 수 있는지 테스트해야합니까?

답변

숫자가있는 경우 n주요 아니라,이 두 가지 요소로 고려 될 수 a및 b:

n = a * b

이제 a과 b의 제곱근보다 두 클 수 없습니다 n다음 제품이 있기 때문에, a * b보다 큰 것이다 sqrt(n) * sqrt(n) = n. 따라서의 인수 분해 n에서 적어도 하나의 인수는 의 제곱근보다 작아야하며, 제곱근 n이하인 요소를 찾을 수없는 경우 n소수 여야합니다.

답변

m = sqrt(n)그때 말해 보자 m × m = n. 이제 경우는 n다음 주요 아닙니다 n같이 쓸 수있다 n = a × b그래서 m × m = a × b. 공지 사항 m반면 실수입니다 n, a그리고 b자연의 번호입니다.

이제 3 가지 경우가 있습니다 :

a> m ⇒ b <m
a = m ⇒ b = m
a <m ⇒ b> m

세 경우 모두 min(a, b) ≤ m. 따라서까지 검색하면 m적어도 하나의 요소를 찾아야합니다 n. 이는 n소수가 아닌 것으로 표시하기에 충분합니다 .

답변

요인이 n의 제곱근보다 크면 n과 같은 다른 요인이 반드시 n의 제곱근보다 작아야합니다.

답변

더 직관적 인 설명은 다음과 같습니다.

100의 제곱근은 10입니다. a와 b의 다양한 쌍에 대해 axb = 100이라고합시다.

a == b이면, 그것들은 동일하며 정확히 100의 제곱근입니다. 10입니다.

그중 하나가 10보다 작 으면 다른 하나는 더 커야합니다. 예를 들어 5 x 20 == 100입니다. 하나는 10보다 크고 다른 하나는 10보다 작습니다.

axb에 대해 생각할 때, 그중 하나가 쓰러지면 다른 하나는 보상하기 위해 커져야하므로 제품은 100을 유지합니다. 그들은 제곱근을 중심으로 피벗합니다.

101의 제곱근은 약 10.049875621입니다. 따라서 숫자 101을 우선 순위로 테스트하는 경우 10을 포함하여 10에서 10까지의 정수만 시도하면됩니다. 그러나 8, 9 및 10은 소수가 아니므로 7까지만 테스트하면됩니다. 초기.

하나의 숫자가 10보다 큰 요인 쌍이있는 경우 다른 쌍은 10보다 작아야합니다. 더 작은 요소가 존재하지 않으면 일치하는 더 큰 계수 101이 없습니다.

121을 테스트하는 경우 제곱근은 11입니다. 소수가 1에서 11까지 (포함) 포함되어 있는지 확인해야합니다. 11은 11 번 들어가므로 121은 소수가 아닙니다. 10시에 멈췄지만 11 번은 테스트하지 않았다면 11 번을 놓쳤을 것입니다.

홀수 만 테스트한다고 가정 할 때 2보다 크지 만 제곱근 이하인 모든 소수를 테스트해야합니다.

답변

n소수 (1보다 큰 숫자)가 아니라고 가정 합니다. 그래서이 번호는 a하고 b그러한

n = ab      (1 < a <= b < n)

관계를 곱 a<=b에 의해 a그리고 b우리가 얻을 :

a^2 <= ab
 ab <= b^2

따라서 : (참고 n=ab)

a^2 <= n <= b^2

따라서 (주 a및 b긍정적)

a <= sqrt(n) <= b

따라서 숫자 (1보다 큰)가 소수가 아니며 수의 제곱근까지의 나누기 성을 테스트하면 요인 중 하나를 찾을 수 있습니다.

답변

주어진 정수 N가 소수가 아니라고 가정 해 봅시다 .

이어서 N은 두 가지 요인으로 인수 분해 가능 a하고 b, 2 <= a, b < N되도록 N = a*b. 분명히, 둘 다 sqrt(N)동시에 보다 클 수는 없습니다 .

일반성을 잃지 않고 a더 작은 것으로 가정합시다 .

이제 N범위 에 속하는 제수를 찾을 수 없다면 [2, sqrt(N)]그 의미는 무엇입니까?

이 수단 N에있는 약수가없는 [2, a]등을 a <= sqrt(N).

따라서, a = 1및 b = n따라서 정의에 의해, N소수 .

…

당신이 만족하지 않으면 더 읽을 거리 :

많은 다른 조합이 (a, b)가능할 수 있습니다. 그들이 있다고 가정 해 봅시다.

(a ₁ , b ₁ ), (a ₂ , b ₂ ), (a ₃ , b ₃ ), ….., (a _k , b _k ). 일반성을 잃지 않으면 서 _i <b _i , 이라고 가정하십시오 1<= i <=k.

이제 N소수가 아니라는 것을 보여줄 수 있다면 _i 를 더 이상 분해 할 수 없다는 것을 보여주는 것으로 충분합니다 . 그리고 우리는 또한 _i <= sqrt(N)이므로 sqrt(N)모든 _i를 덮을 때까지 확인해야합니다 . 따라서 당신 N은 소수 인지 결론을 내릴 수 있습니다 .

…

답변

그것은 실제로 인수 분해와 제곱근의 기본 용도입니다.

추상적 인 것처럼 보이지만 실제로는 비 프라임 숫자의 최대 계승이 다음과 같은 이유로 제곱근이어야한다는 사실에 있습니다.

sqrroot(n) * sqrroot(n) = n.

위의 모든 정수 경우, 점을 감안 1이하 또는 최대 sqrroot(n)균등에 분할은 n다음 n소수가 될 수 없습니다.

의사 코드 예 :

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}