728x90
반응형
코드 1 - i(2 ~ N)를 j(2 ~ i)로 나누기
N을 입력받고 i를 2~N까지 1씩 더한다.
j가 2부터 i에 도달할때까지 1씩 더하면서 i와 나누어 떨어지면 (1과 자기 자신을 제외한 인수가 있으므로) 소수가 아님.
위 연산을 반복해서 0~N 까지 소수의 개수를 하나하나 판단하여 카운팅한다.
각 범위를 계산하며 시간을 측정해본 결과는 아래 표와 같다.
#include<stdio.h>
#include<math.h>
int main() {
int i, j, cnt=0, flag=1;
unsigned int min, max;
// 범위 입력
printf("min : ");
scanf_s("%d", &min);
printf("max : ");
scanf_s("%d", &max);
// 2보다 작은 최소 범위가 입력되면 2로 고정
if (min < 2) min = 2;
printf("입력 받은 범위 내의 소수");
// i가 입력받은 최소 범위부터 최대 범위까지 반복
for (i = min; i < max; i++)
{
flag = 1; // 현재수가 소수라고 가정하고 시작
// j는 2부터 현재의 i 전까지 증가
for (j = 2; j < i; j++)
{
// i와 j를 나눈 나머지가 존재하면 소수가 아님
if (i % j == 0)
{
flag = 0; // flag가 0이면 현재 수(i)는 소수가 아님
break; // 더 이상 j로 나누어 줄 필요가 없으므로 탈출
}
}
// 위에서 판단된 결과가 소수이면(0이 아니면)
if (flag)
{
cnt++; // 개수를 증가시킴 (입력 받은 범위 내의 소수 개수)
printf("%d\t", i); // 출력
if (cnt % 5 == 0)
{
printf("\n"); // 5개 단위로 끊음
}
}
}
printf("\n%d ~ %d 사이의 소수 개수 : %d개\n", min, max, cnt);
return 0;
}
범위 | 개수 | 시간(s) |
2~100 | 25 | 0.000s |
2~1000 | 168 | 0.001s |
2~10000 | 1229 | 0.028s |
2~100000 | 9592 | 0.973s |
2~1000000 | 78498 | 119.606s |
2~10000000 | - | - |
코드 2 - i (2 ~ N)를 j (2 ~ i / j)로 나누기
현재 수 i가 2의 배수일 경우 i/2 * 2 = i, 3의 배수일 경우 i/3 * 3 = i, 5와 7의 배수일 경우는 i/5 * 5 = i, i/7 * 7 = i 가 성립한다. (4, 6등은 2와 3의 배수이므로 해당 범위에 포함된다.)
위 공식을 일반화시키면 아래와 같고,
i/n * n = i
여기서 i의 소인수는 j와 i/j의 곱셈이므로 j는 i/j보다 클 수 없다는 가설을 적용하여 코드를 작성했다.
(수가 커질수록 더 많은 범위의 계산이 생략되므로 속도가 빨라짐)
아래 표를 보면 코드1의 방식보다 좀 더 개선된 걸 볼 수 있다.
#include<stdio.h>
#include<math.h>
#include<time.h>
void test(int min, int max)
{
clock_t start, end;
float res;
int i, j, cnt = 0, flag;
start = clock();
for (i = min; i < max; i++)
{
flag = 1;
// 기존과 달라진 부분, j로 확인 하는 범위를 i와 현재 j의 나눈 몫까지로 줄였음
for (j = 2; j <= (int)(i / j); j++)
{
if (i%j == 0)
{
flag = 0;
break;
}
}
if (flag)
{
cnt++;
}
}
end = clock();
res = (float)(end - start) / CLOCKS_PER_SEC;
printf("%d~%d : %d개\t%.3fms\n", min, max, cnt, res);
}
int main() {
int arr[] = {100, 1000, 10000, 100000, 1000000, 10000000, 1000000000};
for (int i = 0; i < (int)(sizeof(arr) / sizeof(int)); i++)
{
test(2, arr[i]);
}
return 0;
}
범위 | 개수 | 시간(s) |
2~100 | 25 | 0.000s |
2~1000 | 168 | 0.000s |
2~10000 | 1229 | 0.001s |
2~100000 | 9592 | 0.028s |
2~1000000 | 78498 | 0.359s |
2~10000000 | 664579 | 7.392s |
2~100000000 | 5761455 | 202.174s |
2~1000000000 | 50847534 | 5087.694s |
2~10000000000 | - | - |
코드 3 - 에라토스테네스의 체
에라토스테네스의 체를 활용하여 미리 계산된 소수 여부 테이블을 참조하는 방식으로 개수 확인한다.
작은 범위에서는 위의 알고리즘 들과 비슷하거나 느리지만 큰 수의 범위로 가면 훨씬 빠른걸 볼 수 있다.
#include <iostream>
using namespace std;
typedef unsigned long long ll;
/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(ll m) {
bool* arr = new bool[m + 1];
memset(arr, 1, sizeof(bool) * (m+1));
arr[0] = false;
arr[0] = false;
for (ll i = 2; i < m + 1; i++) {
if (arr[i] == true) {
for (ll j = i * 2; j < m + 1; j += i) {
arr[j] = false;
}
}
}
return arr;
}
int main() {
clock_t start, end;
ll N, M;
ll sum=0;
start = clock();
cin >> N >> M;
bool* arr = Sieve_of_Eratosthenes(M);
for (ll i = N; i <= M; i++) {
if (arr[i]) {
sum++;
}
}
end = clock();
float res = (float)(end - start) / CLOCKS_PER_SEC;
cout << "" << N << " " << M << " " << sum << ", " << res << "ms" << endl;
return 0;
}
범위 | 개수 | 시간(s) |
2~100 | 25 | 7.149 |
2~1000 | 168 | 9.231 |
2~10000 | 1229 | 14.213 |
... | - | - |
2~100000000 | 5761455 | 53.387 |
2~1000000000 | 50847534 | 23.744 |
2~10000000000 | 455052511 | 252.08 |
2~100000000000 | - | - |
참고
- 계산 범위의 조절로 100만에서 1억으로 향상되었지만 여전히 큰 수를 처리하기엔 어려움
- 에라토스테네스의 체를 활용할 경우 테이블 생성으로 인해 작은 수 범위에서는 더 오래걸리지만,
큰 수에서는 훨씬 적은 시간이 걸림. (1억에서 100억 단위로 향상됨) - Openssl을 활용한 더 큰 소수의 활용은 아래 블로그에 있다.
728x90
반응형
'코딩테스트 > 알고리즘' 카테고리의 다른 글
[자료구조] 우선순위 큐 - 작성 중 (0) | 2022.04.11 |
---|---|
[알고리즘] 하노이의 탑 (0) | 2022.03.09 |
[알고리즘] DFS/ BFS (0) | 2022.02.05 |
[알고리즘] 달팽이 배열 채우기 (0) | 2021.11.06 |
[알고리즘] 함수 (0) | 2021.10.11 |
[알고리즘] RSA 암복호화 알고리즘 C로 구현하기? (2) | 2020.05.17 |
댓글