kuro11pow2   2달 전

위키피디아에 따르면 소인수분해는 다음과 같습니다.

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.

따라서 소인수분해는 합성수가 아닌 수에 대해서는 정의되지 않습니다. 즉, 소인수분해가 불가능합니다.

출제자의 요구는 소인수분해의 결과를 출력하는 것인데 소인수분해가 되지 않을 경우 어떻게 해야 할까요?

그래서 예시를 살펴보았습니다. 예시에서는 소인수분해가 불가능한 경우 입력 그대로를 출력하고 있습니다.

따라서 1의 경우 소인수분해가 불가능하므로 1을 출력해야 옳습니다.

그러나 현재 1은 1을 출력시 오답처리가 되고 있습니다.

주어진 조건에서 1을 출력해야 하지 않을 이유를 찾을 수 없습니다.

따라서 다음 문구를 추가하거나 입력에서 1을 제외하여 주시기 바랍니다.

"입력이 소수이고 소인수분해되지 않을 경우 입력을 그대로 출력한다"

오답: 22664708

jh05013   2달 전

저는 위키백과의 저 정의에 의문을 제기합니다. 뭔가 엄밀하게 정의하려고 하지 않은 문장 같네요. 같은 문서의 밑에 "By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization."라는 문장이 있는데, 소인수분해를 합성수에 대해서만 정의하면 이 문장은 틀리게 됩니다.

https://en.wikipedia.org/wiki/... 은 "Writing a number as a product of prime numbers is called a prime factorization of the number."라고 하고 있습니다. 이 정의에 따르면 1을 소인수분해하려면 아무 소수도 곱하지 않아야 하고, 따라서 출력이 없어야 합니다.

그렇긴 하나, 1을 조건에서 제외하는 것도 나쁘진 않을 것 같습니다.

kuro11pow2   2달 전

산술의 기본정리 페이지에서는 다음과 같은 문장이 있는데요

In number theory, the fundamental theorem of arithmetic states that every integer greater than 1[3] either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique.

greater than이라는 표현을 쓰고 있습니다. 

단, 3번 주석을 보면 empty product rule 을 적용하면 1을 제외하지 않고, 즉 모든 양의 정수에 대해서 적용할 수 있다고 나와있습니다.

왜 empty product rule을 가정해야 하냐면 소인수분해의 기본 표현 형태를 다음처럼 제시하기 때문입니다.

preview

곱하여 n이 되는 소수의 유한 중복집합이 유일하게 존재한다는 것인데요 아시다시피 위 정의에 따르면 n은 1이 될 수 없습니다.

하지만 이때 양 변에 임의의 p_i^0을 곱해주어도 등호가 성립한다는 사실에서, 곱하여 n이 되는 소수의 유한 중복집합이 공집합인 경우를 1로 정의하자고 말합니다.

Every positive integer n > 1 can be represented in exactly one way as a product of prime powers:

where p1 < p2 < ... < pk are primes and the ni are positive integers. This representation is commonly extended to all positive integers, including 1, by the convention that the empty product is equal to 1 (the empty product corresponds to k = 0).

여기서 empty product를 1로 간주하는 것은 convention이며 그리 직관적이지는 않습니다. 0! =  1처럼 말이죠.

그래서 https://www.acmicpc.net/proble... 에서 0 != 1임을 따로 언급하는 것처럼 명시하는 것이 필요하다고 생각합니다.

kuro11pow2   2달 전

임의의 양의 정수에 대한 소인수분해가 불가능하다는 주장은 철회하겠습니다.

단, 소인수분해를 "곱하여 n이 되는 소수의 유한 중복집합의 원소를 구하는 과정"으로 정의할 때, 해당 집합이 공집합인 경우를 n = 1로 정의하는 것은 증명의 편의를 위한 정의의 확장, convention일 뿐이므로 보다 명확히 하기 위하여 다음과 같은 문구를 추가하는 것을 제안합니다.

"N에 대한 소인수분해란 모두 곱하면 N이 되는 유한 중복집합의 원소를 구하는 과정이다. 단, 해당 집합의 원소는 모두 소수여야 하며, 집합이 공집합일 경우 N은 1로 간주한다."

jh05013   2달 전

Empty product는 매우 보편화된 convention이라고 생각하지만, 이 사이트의 전체 유저 분들에게 직관적인 개념이 아니라는 것에는 동의합니다.

입문용 문제인 만큼, 지문을 모든 사람들이 쉽게 이해할 수 있으면 좋겠습니다. 그래서 2 ≤ N으로 조건을 수정하는 것을 제안합니다.

kuro11pow2   2달 전

동의합니다. 관리자께서는 출제자의 의도에 부합하는 내에서 다음 두 가지 안 중 하나를 채택하여 주시기 바랍니다.

1. 입력 변경

첫째 줄에 정수 N (2 ≤ N ≤ 10,000,000)이 주어진다.

2. 문제 변경

"N에 대한 소인수분해란 모두 곱하면 N이 되는 유한 중복집합의 원소를 구하는 과정이다. 단, 해당 집합의 원소는 모두 소수여야 하며, 집합이 공집합일 경우 N은 1로 간주한다."

댓글을 작성하려면 로그인해야 합니다.