약수와 소수

약수(Divisor)

어떤 정수를 나누어 떨어지게 하는 0이 아닌 정수

 

[예시1] 4의 약수는 1, 2, 4

4 ÷ 1 = 4
4 ÷ 2 = 2
4 ÷ 3 = 1.333···
4 ÷ 4 = 1

 

 

소수(Prime Number)

1과 자기 자신만으로 나누어 떨어지는 1보다 큰 정수. (약수가 1과 자신뿐)

 

[예시2] 2, 3, 5, 7, 11, ···

2의 약수는 1, 2
→ 2 ÷ 1 = 2
→ 2 ÷ 2 = 1

3의 약수는 1, 3
→ 3 ÷ 1 = 3
→ 3 ÷ 2 = 1.5
→ 3 ÷ 3 = 1

4의 약수는 1, 2, 4([예시1] 참고)로 1과 자기 자신 외에도 나누어 떨어지는 수가 있으므로 소수가 아님.

 

에라토스테네스의 체 (Eratosthenes' sieve)

그리스의 수학자 에라토스테네스가 고안한 2부터 n까지의 소수를 찾는 방법.

 

2부터 n까지의 자연수 중, 가장 작은 소수인 2 이외의 2의 배수, 그 다음 소수인 3 이외의 3의 배수, 그 다음 소수인 5 이외의 5의 배수를 순서대로 삭제하면 2부터 n까지의 소수를 보다 빠르게 찾을 수 있다.

 

[예시3] 2~10 까지의 소수 찾기

2, 3, 4, 5, 6, 7, 8, 9, 10

2를 제외한 2의 배수 삭제

→ 2, 3, 4, 5, 6, 7, 8, 9, 10

3을 제외한 3의 배수 삭제

→ 2, 3, 4, 5, 6, 7, 8, 9, 10

5를 제외한 5의 배수 삭제

→ 2, 3, 4, 5, 6, 7, 8, 9, 10

7을 제외한 7의 배수 삭제

→ 2, 3, 4, 5, 6, 7, 8, 9, 10

2~10 까지의 소수는 2, 3, 5, 7.