[펌] 10000000까지의 소수 표와, 구하는 프로그램의 속도를 높여보자.

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초 -_-;;

엄청난 차이가 있습니다.

프로그래밍을 잘하려면 수학적 능력도 필요하다는 것을 절실히 느끼게 해주는 문제이네요.

출처 : 네이버 지식인