소수(Prime Number)란 소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말한다. 아래 표는 100 이하의 소수를 나타내는 표로, 1과 자기 자신 말고 약수가 존재하지 않는다. 총 3가지의 방법으로, 일반 반복문, 제곱근, 에라토스테네스의 체를 이용한 방법을 설명한다. 1. 모든 경우의 수를 전부 나누는 방법 O(n) 이 경우는 판단하는 수를 2부터 그 수까지 모두 나누는 방법이다. 모든 값을 하나하나 약수가 있는지 판단하는 알고리즘으로 구현은 쉽지만 시간 복잡도가 O(n)으로 가장 비효율적이다. bool PrimeNumber(int number) { for(int i = 2; i < number; i++) { // 1개라도 나누어 떨어지면 약수가 존재하므로 false if(n..
