finding_prime2

소수 찾기2

• 문제
• 간단한 문제 설명
  2이상 1,000,000이하 정수 n이 주어질 때, 1부터 n사이에 있는 소수의 개수를 반환하는 문제.
• 내 코드
• 내 코드 설명
  소수는 1과 자기 자신이외 수로 나누어떨어지지 않는 수를 말한다. 따라서 2도 소수인 것을 알 수 있다. 소수가 될 수 있는 조건을 만족하기 위해서는 2로 나누어떨어지면 안된다. 따라서 2 이외의 소수는 홀수인 것을 알 수 있다. 나누어떨어지는 관계를 생각해보면 어떤 수는 몫과 약수의 곱으로 표현 될 수 있으며 직사각형의 넓이를 구하는 공식과 같다. 넓이 100인 직사각형의 약수는 1*100, 2*50, 4*25, 5*20, 10*10, 20*5, 25*4, 50*2, 100*1 이렇게 되는데 10*10 이후는 반복인 것을 알 수 있다. 따라서 100의 약수를 구하기 위해서는 sqrt(100)까지의 수만 확인해 보면 되고, 이 사실로 어떤 수의 약수를 구하기 위해서는 1부터 sqrt(그 수)까지 정수 중 나누어떨어지는 수를 구하면 되는 것을 알 수 있다. 이 개념을 소수를 구하는데 적용할 수 있는데, 2부터 sqrt(자기 자신 - 1)까지 나누어떨어지는 수가 있으면 소수가 아닌 것을 알 수 있다. 그리고 위에서 확인한 사실을 활용해서 2부터 sqrt(자기 자신)까지의 정수 중 홀수만 확인하면 된다. 한가지 더 적용할 수 있는 개념으로 소수들의 곱으로 모든 자연수를 만들 수 있기때문에 2부터 sqrt(자기 자신)의 사이에 있는 소수로 나누어 떨어지는지 확인하면 되고, 그 소수를 p라 했을 때 p <= sqrt(n)를 만족하게 된다. Math.sqrt() 연산보다는 곱하기 연산이 빠르므로 p^2 <= n을 만족하면 된다. 따라서 어떤 수 n이 p^2 <= n를 만족하는 어떤 소수 p로도 나누어떨어지지 않는다면 n이 소수임을 알 수 있다.