2 소수 구하기 알고리즘

소수를 구하는 알고리즘은 약수의 개수로 판단하는 방법과 배수를 지워 가는 방법이 있습니다. 이 두 가지 알고리즘을 살펴보겠습니다.

 

알고리즘 ①

먼저 약수가 2개인 것으로 소수를 판별하는 방법입니다.

예를 들어 10이 소수인지 판단하려면 10을 1, 2, …, 9, 10으로 각각 나누어 보고 나머지가 0인 개수가 2개이면 소수라고 할 수 있습니다. 즉, 10을 1, 2, …, 9, 10으로 각각 나누고 나머지가 0이 나올 때마다 개수를 1 증가시킵니다. 그리고 최종적으로 개수가 2이면 소수리스트에 저장합니다. 즉, 약수의 개수가 2개이면 소수입니다.

 

10은 약수의 개수가 4개이므로 소수가 아니라고 판단합니다. 그렇다면 ‘5는 소수인가?’를 판단하려면 1, 2, 3, 4, 5로 나누어 약수의 개수가 2이면 소수라고 판단하면 되겠지요?