[자료구조] 해시테이블과 소수

테이블 크기를 소수로 하는 이유.

소수가 아닌 수 A라고 가정해 보자. 

그렇다면 A의 모든 약수는 자신의 배수가 곧 키값이 된다.

예를 들면, 12로 Mod 연산을 한다고 했을 때,

12의 약수

input : 3 6 9 12 15 18 21 24 ...

output : 3 6 9 0 3 6 9 0...

input : 4 8 12 16 20 24 ...

output : 4 8 0 4 8 0 ...

input : 6 12 18 24 30 36 ...

output : 6 0 6 0 6 0 ...

이런 식이다.

하지만 소수는 약수가 1과 자신 뿐이므로 약수의 배수가 항상 약수로 나오는 문제가 제외된다.