우선 가장 먼저 생각해볼 생각.
#include<iostream>
using namespace std;
int main()
{
int i, n;
unsigned long long counter = 0;
for (n = 2; n <= 1000; n++)
{
for (i = 2; i < n; i++)
{
counter++;
if (n % i == 0)
break;
}
if (n == i)
cout << n << '\n';
}
cout << "나눗셈 실행 횟수 : " << counter;
return 0;
}
만약 n의 숫자가 9라고 가정해보자.
9는 안쪽 for문에서 i = 3일 때 break 동작되어서 n == i 가 안되서 소수가 아니다.
n이 13이라면 ? i = 2 ~ 12까지 작동했을 경우 걸리지 않아서 n == i 가 성립되어서 소수가 된다.
그런데 여기서 중요하게 생각해볼 지점은
n이 2 또는 3으로 나누어 떨어지지 않는다면, 이 해당 수의 배수들인 4나 6으로도 나누어 떨어지지 않는다.
즉, 예를 들어 2로 나누어 떨어지지 않는다면, 굳이 4 6 8 10 등등을 나눌 필요가 없다는 소리다.
하지만 위의 코드는 그 경우들도 다 포함하고 있으므로 계산 시간이 길어진다.
이를 효율적인 코드로 수정하기 위해 가져야할 건 위에 언급한 소수들의 나눗셈만으로도 충분하다라는 것이다.
1 개선안)
소수를 구하는 과정에서 그 때까지 구한 소수를 배열에 저장하고
배열에 저장되어 있는 소수들로 나눗셈을 진행하는 것이다.
배열에는 소수들이 점점 쌓이게 된다.
#include<iostream>
using namespace std;
int main()
{
int i, n;
int prime[500];
int ptr = 0;
unsigned long long counter = 0;
prime[ptr++] = 2;
for (n = 3; n <= 1000; n += 2)
{
for (i = 1; i < ptr; i++)
{
counter++;
if (n % prime[i] == 0)
break;
}
if (ptr == i)
prime[ptr++] = n;
}
for (i = 0; i < ptr; i++)
cout << prime[i] << '\n';
cout << "나눗셈을 실행한 횟수 : " << counter;
return 0;
}
이러면 소수만 가지고 나눗셈을 했기에 연산수가 확실히 줄어든다.
2 개선안)
우리가 초등학교 고학년? (나는 5학년 때 배수 약수 배운 것 같은데..)
그 때 16의 약수를 써보라고 하면
1 2 4 8 16을 쓴다. 근데 글씨 쓰는 순서를 정말로 '1 -> 2 -> 4 -> 8 -> 16'으로 쓰기 보다는
'1 ->16 -> 2 -> 8 -> 4' 이렇게 쓰는 경우가 많다.
어떤 말을 하고 싶냐면.. 4를 보면 지금 16의 제곱근이다. 우리가 굳이 4 초과의 숫자들을 추가적으로 나누는 연산을 할 필요없이, 1 2를 한다면 8 16은 저절로 따라오는 것이고 우리는 소수를 판별하기 위함이므로 굳이 그 이상을 나눠볼 필요성이 없다는 이야기다.
즉, 'n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다'를 만족하면, 소수인 것이다.
sqrt함수를 활용해서 제곱근을 써도 될 듯 싶다.
#include<iostream>
using namespace std;
int main()
{
int i, n;
int prime[500];
int ptr = 0;
unsigned long long counter = 0;
prime[ptr++] = 2;
prime[ptr++] = 3;
for (n = 5; n <= 1000; n += 2)
{
bool flag = false;
for (i = 1; counter++, prime[i] * prime[i] <= n; i++)
{
counter++;
if (n % prime[i] == 0)
{
flag = true;
break;
}
}
if (!flag)
prime[ptr++] = n;
}
for (i = 0; i < ptr; i++)
cout << prime[i] << '\n';
cout << "연산 횟수 : " << counter;
return 0;
}
'백준 문제풀이 > 알고리즘 정리' 카테고리의 다른 글
C++ 알고리즘 강의 - 2주차(그래프이론, DFS, BFS, 트리순회) (0) | 2022.07.09 |
---|