알고리즘 - 소수 부수기!

소수

나를 괴롭히는 소수를 부수자

간단한 소수 찾기

소수란 자신과 1만 나누어지는 수다. 즉, 약수가 있으면 소수가 아니다.
n을 i로 나누다 약수가 나오면 false를 한다.

-> 하나씩 다 확인하기 때문에 시간 복잡도는 O(N)

여기서 절반만 검사할 수 있는 방법이 있는데 바로 제곱을 이용하는 것이다. 모든 약수는 대칭 형태다. 예를들어 8은 4 2 = 2 4로 나타낼 수 있다는 것!

그 수의 제곱근까지 검색해보면 된다!!!

여러 소수 찾기

• 에라토스테네스의 체

• 모든 수를 배열에 넣고 2, 4, 6 등 소수가 아닌 수의 배수만 거르고 걸러 소수만 남기는 것. 말그대로 체 처럼 탈탈탈 털어서 소수만 남긴다.

깔끔하고 아름답다..

• 결과

효율성에서 다 막혔다.

• 해결

도대체 무슨 효율인 줄 몰라서 해매다가 블로그 글 중에 0과 1 때문이라는 걸 보고 첫 배열에 0부터 넣어주고 나중에 0,1을 바꿔줬다!

--> 즉, 원래는 2부터 검사해서 배열에 0,1이 empty item으로 되었는데 (그래서 for문이 계속 돌았나봄) 0,1을 넣어주고 나중에 바꿔서 우리 까탈스러운 컴퓨터가 할 일을 덜어주었다.

• 최종