컴공 일기 246
게시글 주소: https://orbi.kr/00068783679
… 예… 오랜만에 들어와서 요새 풀고 있는 알고리즘 코드 하나 올려놓고 갑니다…
여전히 꽤…는 아니어도 열심히는 사는 중입니다…
간단한 해설을 하자면 소수를 찾는 알고리즘입니다.
주로 Sieve of Eratosthenes, 에라토스테네스의 체라고 얘기합니다. 컴퓨터에서 소수를 찾는 여러가지 방법이 있습니다만, 학부 수준에서 가장 이해하기 쉽고 직관적인 알고리즘이라고 할 수 있겠네요.
소수가 아닌 게 확실한 수를 지워나가는 방식입니다. 그래서 ‘체’라는 말을 쓰죠. 걸러낸다는 거예요.
그럼 뭘 걸러내면 될까요? “배수”들을 걸러내는 겁니다.
2의 배수, 3의 배수, 4의 배수, 5의 배수, 6의 배수…. 등등 전부요.
예를 잠깐 들어볼까요? 만약에 1부터 100까지의 자연수 범위에서 소수를 찾고 싶으면, sqrt(100) 즉 10의 배수까지 다 지워내면 됩니다. 어? 100까지니까 100의 배수까지 지워야 되는 게 아니냐고요?
사실 맞습니다만, 10의 배수까지만 탐색해도 전부 탐색할 수 있습니다. 만약 N이 소수가 아니라서 a * b의 형태를 이룬다면 즉, N = a * b 라면, a와 b의 최댓값은 루트 N입니다. a와 b는 모두 자연수이기 때문이지요. 만약 둘 중 한 수가 루트 N을 초과하는 순간, a * b의 값은 N을 넘어서게 됩니다. 따라서, 루트N까지 탐색의 범위를 제한해도 무방합니다.
에라토스테네스의 체는 이중반복문으로 구현이 되어서 얼핏 O(N^2)의 부담스런 시간복잡도를 가지는 듯 하지만,
실상은 그렇지 않습니다. 왜냐하면 대다수의 경우가 if(prime[i] == 0) continue;를 충족시키기 때문이지요…
말하자면 그 전에 지워낸 게 많아서, 새로운 배수에서 소수가 아닌 수를 지울 때, 탐색해야 할 후보군이 많이 없다는 뜻입니다.
그 효율성 때문에 알고리즘 문제에서 자주 이용된다.. 뭐 그리 생각하면 됩니다.
오늘도 재미있는 공학 시간..
#include <iostream>
#include <cmath>
#define MAX 1000001
using namespace std;
int prime[MAX];
int n, a, b, result;
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
for(int i=2; i<MAX; i++)
{
prime[i] = i;
}
for(int i=2; i<sqrt(N); i++)
{
If(prime[i] == 0) continue;
for(int j=i * i; j < MAX; j+=i)
{
prime[j] = 0;
}
}
while(1)
{
cin >> n;
if(n == 0) break;
for(int i=3; i < MAX; i++)
{
if(prime[i] != 0)
{
if(n - prime[i] != 0)
{
a = i;
b = n - prime[i];
break;
}
}
}
cout << n << " = " << a << " + " << b << "\n";
}
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
입대하는 10월 전까지 최대한 많은 모의고사를 만들어서 오르비 유저 분들을 포함한...
-
기울기를 이용하지 않고 푸는게 기울기 이용한거보다 어렵나요?
-
카의vs고의 5
카의호소인으로서 솔찍히 무조건 카의라고 생각하지만 그래도 인지도 면에서는 sky빨...
-
드릴5랑 비슷하거나 약간 더 어려운 둣
-
점심 먹을지 저녁 먹을지 고민인데
-
쫑느 현장에서 듣고 싶엉엉엉?? 오늘 물어봣더니 300번대임..
-
미치겠다 인형 안아도 막 심장 빨리 뛰고 그러네요
-
일단 난 아님
-
나 사랑해주는 사람 마음 긁는거만큼 쓰레기인 짓이 없구나 남은 인생 효도하면서 살아야지
-
반수 4주차 기록 국어 21, 27틀 수학 28, 30틀 영어 30틀 생명 8,...
-
. 2
굿나잇
-
9월 중순쯤부터 들으려면 한달 전부터 대기걸면 될까요? 주말이라 내일 문의해보긴 하려구여
-
현역 국어 언매 2~3 등급 뜨는 허순데 항상 푼거 정답률은 괜찮은데 시간 관리가...
-
영어 막장구원 1~10일차 복습 TEST 스피드보카 3일차 사문 스피드개념 9~10강
-
몇 주째 이러는데 해결법 없나… 사장님한테 문자했는데 단체 알림 보내셔도 소용없음
-
일진하고 어울리고 양아치같이 담배도 피우고 술도 하지만 막상 일진은 아니고 좀 잘...
-
ㅋㅋㅋ 롤하면서 들어야겠다
-
야식먹고싶다.. 5
로제떡볶이에 별빛청하 먹고싶어요
-
지금 7모2등급이고 6모3등급인데 뉴런을 다시한번들어야할까요 기출은 다시 안플어도 되겠죠
-
블라인드 처리되지 않은 게시글입니다
군대에서 코딩은 어떤 앱으로 하고 계신가요?