Prime / Composite | 소수와 합성수

 

 

소수 합성수 그리고 루트

---

KH 당산지원에서의 10일차.

가끔은 쉬운 문제로 흐뭇해 하기도, 어려운 문제로 고민에 빠질 때도 있지만 모두 깨달음의 연속이였기에 그 순간순간이 행복했다.

 

소수와 합성수 그리고 그를 연산하는 과정에 대한 이해를 하기 전까지는 말이다.

 

소수와 합성수는 무엇일까?

소수는 1 과 자기 자신으로만 나누어지는 수이고, 합성수는 1과 자기 자신을 포함한 다른 수로도 나누어지는 수를 합성수라고 한다.

(여기서 나누어진다는 것은 나머지 값이 0이라는 의미이다.) (더 자세한 이론은 꺼무위키에서)

 

그래서 간단한 예시들을

들어보자면,

 

소수 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ...

합성수 : 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24 ...

 

이런 식으로 구성되어 있고, 여기서 2는 소수에서 유일한 짝수이며 2를 제외한 모든 짝수들은 합성수이다.

문제는 이거다.

어떻게 하면 컴퓨터가 연속되는 이 모든 숫자들이 소수인지 합성수인지 확인할 수 있게 만들지?

즉, 내가 어떻게 이걸 연산해서 코드로 옮겨 적지? 가 가장 큰 벽이였다.

 

하지만 사람은 시간이 약이고, 모든 일에는 때가 있는 것 처럼 이 또한 그냥 계속 반복하고 생각하다 보니 풀 수 있고, 이해 할 수 있게 되었다.

 

그렇다면 어떻게 ?

---

 

먼저 앞서 말한 소수와 합성수의 특징을 파악한다면 조금 더 쉽게 문제를 해결할 수 있을 것이다.

 

소수는 1과 자기 자신을 제외한 나머지 수로 딱 나누어 떨어지지 않는다.

 

즉, 소수는 1 부터 소수 자기 자신 사이의 모든 수를 나누었을 때

나머지가 0이 되는 경우는 2가지 뿐이며 이걸 0의 개수로 센다면 0은 총 2개다.

 

그렇다면 합성수는 소수의 반대니까 무조건 0의 개수는 2개 이상이라는 말이다.

 

예를 들어, 8이 소수인지 합성수인지 확인해보자. (사람은 보자마자 합성수라는걸 알지만 컴퓨터는 아니다.)

 

8 / 1 = 8 (0)

8 / 2 = 4 (0)

8 / 3 = 2 (2)

8 / 4 = 2 (0)

8 / 5 = 1 (3)

8 / 6 = 1 (2)

8 / 7 = 1 (1)

8 / 8 = 1 (0)

 

8을 1 부터 8 까지 나누었을 때 나머지가 0이 되는 경우는 4 경우이다.

 

1 , 2 , 4 , 8

 

하지만, 모든 수는 1 혹은 자기 자신으로 자신을 나누었을 때 나머지는 무조건 0이다. 그러니 이 경우는 제외하고

2 부터 (자기 자신 - 1) 사이의 모든 수를 나눴을 때 0이 한개라도 나오면 그 수는 무조건 합성수이다.

왜냐면 이미 1과 자기 자신으로 나누었을 때 0이 2번 나왔고, 소수는 나머지값이 0인 경우는 딱 2개이기 때문이다.

 

이제 코드로 확인해보자 !

---

 

나는 자바의 이클립스를 통해 확인해보려고 한다.

int d = 8; count[2] = 0; for (int i = 2; i < d; i++) { if (d % i == 0) { count[2]++; if (count[2] >= 1) { break; } } } if (count[2] == 0) { System.out.println(k + " = 실수"); } else { System.out.println(k + " = 합성수"); }

int d = 8; count[2] = 0;

for (int i = 2; i < d; i++) { 
	if (d % i == 0) { 
    	count[2]++; 
        if (count[2] >= 1) { 
        break; 
        } 
    }
} 

if (count[2] == 0) { 
	System.out.println(k + " = 실수"); 
} else { 
	System.out.println(k + " = 합성수"); 
}

 

for 문을 살펴보면 i는 2부터 시작한다. 왜 0 혹은 1부터 시작하지 않느냐고?

앞서 말했던 것 처럼 모든 숫자는 1과 자기 자신으로 나누었을 때 무조건 나머지 값이 0이기 때문이다!

굳이 할 필요없는 연산을 컴퓨터에게 시킬 필요가 없다! 느려지니까!

 

같은 이유로 i 가 d 와 같은 값이 될 때 까지 반복하지 않는다. 굳이 할 필요가 없으니까!

그런 이유들로 저 코드는 숫자가 합성수인지 판별하는 코드라고 할 수 있겠다.

 

자, for 문 안의 if 문을 살펴보면, d 와 i 를 나누었을 때 0일 경우 count를 +1 하라고 했고,

그 다음 if 문에서는 만약 count 의 값이 1 이상이 될 경우에는 for 문의 반복을 멈추라고 했다.

 

왜냐하면 2 부터 (자기 자신 - 1) 만큼 숫자들을 연산 했을 때 0이 1개 이상 나오면 합성수이기 때문에 그 이상 연산할 필요가 없기 때문이다.

 

이 코드는 문제없이 잘 돌아간다. 다만 문제인 것은 for 문 안에 if 문 안에 if 문이 들어가 있다는 것이다.

 

if< if <for

 

그렇게 되면 코드를 처음 보는 사람은 이해하기까지 꽤나 오랜 시간이 걸린다.

 

그렇다면 이 코드를 간소화 할 수 없을까?

당연히 가능하다. 바로 루트를 이용해서 for문에 이식하는 방법이다.

 

그러면 그 루트라는게 뭔데?

---

사실 나도 아직 정확히 이해하지 못했다. (그런 경우에는 나무위키)

 

루트4 = 2 * 2

루트9 = 3 * 3

루트16 = 4 * 4

루트25 = 5 * 5

 

이렇게 루트 안에 있는 숫자 x 는 어떤 숫자 a 의 제곱근이다.

 

이제 소수와 합성수 연산에 응용해보자.

앞서 말했듯이 8을 예시로 들겠다.

 

8 / 1 = 8 (0)

8 / 2 = 4 (0)

8 / 3 = 2 (2)

8 / 4 = 2 (0)

8 / 5 = 1 (3)

8 / 6 = 1 (2)

8 / 7 = 1 (1)

8 / 8 = 1 (0)

 

여기서 8을 2로 나누었을 때와 4로 나누었을 때는 나머지 값이 0이다.

즉, 2 * 4 = 8 과 4 * 2 = 8 이 같다는 말이다. 그래서 8의 경우 8을 2로 나눈 이후로 연산되는 숫자를 볼 필요가 없이 8은 합성수라는 말이 된다.

그렇다면 for 문에 어떻게 이식할 수 있을까?

 

지금까지 for 문은 i 가 d 보다 작을 경우에 + 1 씩 하면서 반복된다. 하지만 위의 코드와 같은 이유로 만약 반복 중에 0이 하나라도 나오게 되면 그 수는 합성수인 것 처럼, 0이 한번이라도 나온 이후의 숫자에 대한 나머지 연산은 확인 할 필요도 없게 되는거다.

 

그래서 반복의 범위를 반으로 줄여버리자는 셈이된다.

 

8을 생각해보면,

i = 2 ; i * i <= 8; i++ 의 공식으로 반복한다고 하면

 

i = 2; 2 * 2 <= 8; i++ => 참

i = 3; 3 * 3 <=8; i++ => 거짓

 

이미 8을 2로 나머지 연산을 했을 때 0이 나왔으며, 반복 범위 또한 넘어갔기 때문에 그 이후의 숫자에 대한 연산은 하지 않게 된다.

 

9를 예시로,

 

i = 2; 2 * 2 <= 9; i++ => 참

i = 3; 3 * 3 <=9; i++ => 참

i = 4; 4 * 4 <= 9; i++ => 거짓

 

9는 2로 나머지 연산을 했을 땐 0이 아니고, 3으로 나머지 연산을 했을 때 0이 나온다. 그러면 그 이후의 숫자들의 연산을 볼 필요도 없어지게 된다.

그래서 루트공식을 이용해 반복문의 횟수를 줄여버리는거다. 이 말은 즉, if 문을 사용해 0 이 1개 이상 나올 경우 for문을 멈추라는 말과 같은 말이다.

 

소수의 경우도 마찬가지다.

 

5를 예시로,

 

i = 2; 2 * 2 <= 5; i++ => 참

i = 3; 3 * 3 <=5; i++ => 거짓

 

5를 반으로 접었을 때 2.xxxxx 가 나오는데, 이 말인 즉슨 5 % 2 의 결과가 소수의 결과이기에 이 이후의 연산은 5 % 2 결과값과 같으므로 5 % 2 연산 하나만으로 충분히 판별 가능하다는 말이 된다.

 

그럼 이제 루트를 이용한 코드를 보여줘 !

---

int e = 8; count[3] = 0; 

for (int i = 2; i * i <= e; i++) { 
	if (e % i == 0) { 
    	count[3]++; 
    } 
} 
     
    if(count[3] == 0) { 
    	System.out.println(e + " = 소수"); 
    } else { 
        System.out.println(e + " = 합성수"); 
    }

 

아까 루트를 사용하지 않은 코드에 비해 코드의 수가 훨씬 줄었고 더 간결해졌다.

이 코드에서 e 에 아무 숫자를 대입하면 그 숫자가 소수인지 합성수인지 루트의 공식을 이용해서 연산이 가능하다.

 

느낀점은 ?

---

정말 내가 생각치도 못했던 삶의 여러부분들에 수학이 고스란히 들어가 있구나라는걸 처절히 깨닫게 된 날이다.

그리고 우리가 살아가는 이 모든 순간들은 논리로써 구성되어 있다는 것을 조금이나마 이해할 수 있게 된 계기가 되었다.

세상에는 '그냥' 이라는 건 없다. 모든 것에는 이유가 있고, 그 이유로 인해 현재의 결과가 있는 것이다.

 

우리의 삶도 그러한 것 같다. 본질을 알아야 그 다음으로 더 발전할 수 있다. 우리는 지금껏 그 얼마나 본질을 무시하며 앞만 보고 달려왔는가?