[알고리즘] 소수 구하기

소수: 1과 자기자신(n)만을 약수로 가지는 수

 

방법 1) 2~n-1까지 모든 수를 다 나눠보며 나눠 떨어지지 않으면 소수다.

방법 2) 메모제이션 이전까지의 모든 소수로 나눠 떨어지지 않으면 그 수는 소수다.

방법 3) 제곱근 2~루트n 사이의 수를 다 나눠보며 나눠 떨어지지 않으면 소수다.

방법 4) 에라토스테네스의 체  n^1/2 이하의 수의 배수를 다 지운후 남아있는 수가 소수다.

 

참고사이트

https://velog.io/@hyeon930/%EC%86%8C%EC%88%98%EB%A5%BC-%EA%B5%AC%ED%95%98%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://coding-factory.tistory.com/367

https://danidani-de.tistory.com/50