71쪽 알고리즘 플로차트에서 6번 D>E 이분분에서 질문입니다
16번에서 몫을 B에 대입해서 다시 5번 앞으로 돌아왔을때
왜 다시 D값을 2로 초기화해서 나누지 않나요?
제수가 피제수의 제곱근보다 크면 피제수 자체가 입력받은 수의 소인수라는 말이
잘 이해가지 않습니다
안녕하세요.
4번 동그라미는 피제수를 2부터 나누기 위해 D를 초기화되는 부분으로
소인수로 분해할 B가 소수라면 즉 NMG가 0이 아니라면 10번 동그라미 과정에서 NO가 되어 D가 증가됩니다.
하지만 소수가 아니라면 NMG가 0이 되어 소인수 분해되는 과정이 진행되는데,
예를 들어 50을 소인수 할 때 먼저 2로 나눈 나머지가 0이므로 소인수 분해 값으로 A배열에 2가 저장된 후
몫인 25가 B에 저장됩니다. 이때 아직 D가 2이므로 다시 D를 초기화할 필요없이 다음 값인 25(B)를 D로 나누게 되므로 결국 2부터 나누게 되는 것이죠.
25를 나누는 과정에서 나머지가 0이 아니므로 D가 2~5까지 증가되면서 진행됩니다. D가 5일 때 나머지가 0이 되므로 A배열에 5가 저장된 후 몫인 5가 B에 저장됩니다. 이후 E, 즉 현재 몫인 5의 제곱근이 2인데 이는 현재 D 값보다 2작으므로 B 자체가 소인수가 되어 7번 동그라미 과정을 거친 후 A배열에 5가 저장되어 최종적으로 2, 5, 5의 소인수 분해 과정이 완료됩니다.
오늘도 즐거운 하루 되세요.
-
*2016-10-07 09:36:39
안녕하세요.
4번 동그라미는 피제수를 2부터 나누기 위해 D를 초기화되는 부분으로
소인수로 분해할 B가 소수라면 즉 NMG가 0이 아니라면 10번 동그라미 과정에서 NO가 되어 D가 증가됩니다.
하지만 소수가 아니라면 NMG가 0이 되어 소인수 분해되는 과정이 진행되는데,
예를 들어 50을 소인수 할 때 먼저 2로 나눈 나머지가 0이므로 소인수 분해 값으로 A배열에 2가 저장된 후
몫인 25가 B에 저장됩니다. 이때 아직 D가 2이므로 다시 D를 초기화할 필요없이 다음 값인 25(B)를 D로 나누게 되므로 결국 2부터 나누게 되는 것이죠.
25를 나누는 과정에서 나머지가 0이 아니므로 D가 2~5까지 증가되면서 진행됩니다. D가 5일 때 나머지가 0이 되므로 A배열에 5가 저장된 후 몫인 5가 B에 저장됩니다. 이후 E, 즉 현재 몫인 5의 제곱근이 2인데 이는 현재 D 값보다 2작으므로 B 자체가 소인수가 되어 7번 동그라미 과정을 거친 후 A배열에 5가 저장되어 최종적으로 2, 5, 5의 소인수 분해 과정이 완료됩니다.
오늘도 즐거운 하루 되세요.