알고리즘/Java
JAVA [자바] - 소수 구하는 알고리즘 및 구현
JAVA [자바] - 소수 구하는 알고리즘 및 구현
2020.04.15들어가기 전에 소수 [Prime Number] 소수의 정의는 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미한다는 점은 누구나 알고 있을 것이다. 즉, 소수의 약수는 2개만을 갖고, 그 중 하나는 반드시 1 이며, 나머지는 자기 자신만을 약수로 갖기 때문에 만약 1 보다 크고 자기 자신의 수보다 작은 자연수를 약수로 갖게 된다면 이는 합성수라고 한다. 그리고 위의 개념을 확장해본다면 합성수는 3개 이상인 자연수의 곱으로 이루어져 있으며 소수로 이루어진 곱으로 표현할 수 있다. 그리고 이를 소인수분해라고 한다. 더욱 개념을 넓혀볼까. 소수는 1과 자기 자신만을 약수로 갖고, 합성수는 3개 이상인 자연수의 곱으로 이루어져 있으며 소수들로 이루어진 곱으로 표현할 수 있다고 했다. ..