728x90 반응형 java 소수인지1 소수(Prime Number)인지 아닌지 확인하는 코드 JAVA로 구현하기 소수 소수는 1과 자기 자신만을 약수로 가지는 자연수를 의미한다. 사실 생각해보면 아주 간단하다. 하지만 이걸 막상 코드로 작성하려고하면 한 번 고민을 해봐야 한다. N이라는 숫자가 소수인지 아닌지를 return하는 함수를 만든다고 가정해보자. (1) 2 ~ N-1 을 싹 다 넣어서 약수인지 아닌지 확인하면 된다. 참고로 약수인지는 나눠서 나머지가 0이면 약수인 것이다. 하지만 이 과정은 너무 계산이 길다. Big O 로 적으면 O(n) 이를 조금 줄여보자. 가장 쉽게 생각할 수 있는 방법은 절반을 나누는 방법이다. 하지만 한 번만 더 생각해도 정말 바보같은 생각임을 알 수 있다. 약수라는 것은 곱으로 이루어져있기에 말이다. 곱으로 이루어져있다는 아이디어를 활용하면 아주 간단해진다. 만약 N의 약수가 있.. 2022. 1. 13. 이전 1 다음 728x90 반응형