728x90 소수 판별 알고리즘1 에레스토테네스의 체 안녕하세요. 옆집컴공생입니다. 오늘은 범위 내에 소수를 전부 구해주는 에레스토테네스의 체를 배워 보겠습니다. 소수란 영어론 Prime Number(프라임 넘버) 라고 하는 '약수가 1과 자기자신 뿐인 수'를 의미합니다. 예로 들면 2,3,5,7 등이 있겠습니다. 간단한게 소수를 구하는 반복문을 볼까요? 다음 함수는 x가 소수이면 true , 합성수(소수가 아닌 수)이면 false를 반환해주는데요. 1과 x를 제외한 나머지 모든 수를 for 문으로 돌면서 나누어지는 체크해보는겁니다. 사실 이 방법은 굉장히 오래 걸리는 편인데요. 사실 소수를 판별하는데는 소수의 제곱근 까지만 체크를 해주면 됩니다. 왜일까요? 합성수를 20을 생각해봅시다. 20의 약수는 2, 4, 5 ,10 입니다.( 1과 자신은 제외했습니.. 2020. 6. 9. 이전 1 다음 728x90
