10000000까지의 소수는 직접 적어드릴수는 없습니다.
10000000까지의 소수의 개수는 정확하게 664579개입니다.
이 글에서는, 소수 구하는 프로그램 소스는 가르쳐 드리지 않습니다.
중간중간에 써드리는 소스 만으로도 충분히 짜맞추실수 있기 때문이죠.
소수 구하는 법을 아시는 분만 보시기 바랍니다.
C++ 배우시는 분들이라면 소수 구하기는 80% 이상 해보셨을 겁니다.
일반적으로, 100 정도밖에 안 구해 보셨을텐데요..
그렇기 때문에 속도 차가 별로 나지가 않죠.
하지만, 구하는 범위가 아주 넓어진다면 어떨까요??(이런.. 드라군 놀이가 생각나는걸..)
시간차가 많이 날겁니다.
죄송한 말씀이지만, C++를 처음 다루시는 분들이라면 정중히 뒤로 버튼을 누르라고 할께요.
소수 구하는 프로그램을 짤때의 실수 유형을 봅시다!
[1차원 배열을 사용해서 푸는 분들..]배열을 사용하는 방법은 작은 수에서는 상관이 없지만,
10만이 넘어가는 경우에는 오류가 납니다.
배열을 쓰시면 안되고, Check라는 변수를 만드세요!
Check=0;
if(i%j==0) Check=1;
Check방을 0으로 초기화합니다. 그리고, i를 j로 나눕니다(꼭 i, j가 아니여도 됩니다.)
그리고, i를 j로 나눴을대 나머지가 0이라면 결국 나누어 떨어진다는 말이므로,
Check방을 1로 만듭니다. 그리고 그 아래부분에 이런 코드를 삽입해보죠.
if(Check==1) break;
한번이라도 나누어 떨어졌다면, 밖으로 튕겨 버리세요.
(계속 해봤자 소수가 아니기 때문에 시간 낭비입니다.)
그러면, 본격적으로 들어갑시다!
[나누는 수를 몇까지 해야 할까?]일반적으로 소수는 에라토스테네스의 체 방법을 사용하죠.
하지만, 이 방법은 시간이 조금 오래 걸린다는 단점이 있습니다.
하지만, 가장 쉬운 방법이기도 하죠.
쉽고, 빠르게 하는 방법이 있을까요?
예! 있죠, 나누는 수의 범위를 바꿉시다.
다음 코드를 볼까요?
for(i=2;i<=10000000;i++){
check=0;
for(j=2;j<=i;j++){
check방은 아까 설명 드렸을 겁니다. 초기화 시키는 것이죠.
다중 for문을 사용했는데요, i 나누기 j 를 해서 값을 구할 것입니다.
초보자 분들이시라면 저렇게 짜셨을 겁니다.
그러면, for(j) 부분을 살펴 봅시다~!
그 부분이 나누는 수 부분이 되겠지요.
소수를 판별하려면 어디까지 다 나눠보아야 할까요?
5라는 수가 있습니다. 일반적으로, 이 수가 소수인지 아닌지 판별하려면
2부터 4까지 모두 나눠보게 되죠.
(자기 자신과 1은 나누어 떨어지기 때문에 생략해야 합니다.)
5÷2, 5÷3, 5÷4 <= 3번 계산을 하게 됩니다.
물론, 3번 정도야 0.01초도 안걸리지만, 숫자가 무지하게 커진다면 어떨까요?
저같은 경우는 1000만까지의 소수를 구해보려고 합니다.
1000만개를 모두 나눠 보아야 할텐데, 언제 다 하겠습니까..
그래서, 더 효과적인 방법을 찾아보자는 겁니다.
1. for(j=2;j<=i/2;j++)
이 방법은 아까 전보다는 시간을 2배 절약할 수 있습니다.
이 방법도 정답이 틀리지는 않죠.
왜냐하면, 어떤 수의 2분의 1보다 약수는 1개밖에(자기 자신) 없기 때문이죠.
어떤 수의 2분의 1보다 큰 약수가 2개라면
1개는 자기 자신이고, 나머지 1개는 어떤수의 2분의 1보다는 큰수.
0
정도로 식이 만들어지겠네요.
j 의 값들 중에서, 자연수는 존재하지가 않기 때문에, 이렇게 해도 된다는 것입니다.
하지만, 이것보다 효과적인 방법이 있을까요?
예! 있습니다!
바로, 그 수의 제곱근 까지만 구해보면 됩니다.
이것은 제가 직접 증명은 못해드리지만, 적당히 해보시면 답이 똑같다는 것을 알수 있습니다.
제곱근은 대략 √ 요녀석을 말합니다.
제곱근 함수를 쓰시려면, #include 로 하나를 더 불러와야 하는데요,
math.h 를 불러와야 합니다.
#include[math.h] 처럼요.
[는 <로 바꿔주셔야 하는거 아시죠?sqrt(a)
라고 쓰시면, a 의 제곱근이 구해집니다.
그러면, 이렇게 변신하겠죠.
for(j=2;j<=sqrt(i);j++){
그러면 얼마나 속도가 향상될까요?
제가 위의 세방법의 시간을 모두 재봤습니다.
1번째 방법 : 측정 불가 (1시간 이상)
2번째 방법 : 27분
3번째 방법 : 1분 24초 -_-;;
엄청난 차이가 있습니다.
프로그래밍을 잘하려면 수학적 능력도 필요하다는 것을 절실히 느끼게 해주는 문제이네요.