15. 소수의 개수

it 취업을 위한 알고리즘 문제풀이

문제

코드1

코드2

문제해결방법

• isPirme함수 (주어진 숫자x가 소수인지 확인하는 함수)
  • flag 변수로 prime 변수사용
  • 2~x-1이 까지 숫자로 나누었을 때 나누어 떨어지는 수가 존재한다면 소수가 아님
  • 나누어 떨어지는 숫자가 없었을 경우 소수임
  • 그런데 이때 103같은 소수의 경우 102이까지 모두 체크해야 소수임을 확인할 수 있는데 시간복잡도 측면에서 좋은 코드가 아님
  • 약수의 규칙을 이용해서 코드 2 처럼 수정
  • 64의 경우 (1,2,4,8,16,32,64) 1과 64, 2와 32, 4와 16이 짝을 이루고 8이 중간에 있다 8 다음의 숫자들에 대해서는 나누어 봐야 약수는 이미 구해졌다는 뜻이다.
  • 여기서 8은 64의 제곱근이다. 제곱근을 구하는 함수를 이용해 i가 x의 제곱근까지만 나누어떨어지는 숫자가 있는지 확인하면 되지만 제곱근 함수를 사용하지 않는다면 i를 제곱한 숫자(i*i)가 x를 넘어간다면 더 이상 나누어 떨어지는 숫자를 확인하지 않아도 된다는 뜻이다.
• 2부터 n까지의 숫자에 대해 반복문으로 소수인 경우 cnt 변수를 1씩 증가