컴공 일기 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를 선물하세요.
-
나만어려움??????? 2회 푸는데 14 15 턱막히더니 21 케이스 하나 빠뜨려서...
-
히히 똥 발싸 3
발싸 히히
-
꽤 색다름. 나는 지금까지 문학을 푸는데에 정형화된 방법이 없었는데, 문학을 대하는...
-
그래도 8시간은 했네..
-
어려운 27번 정도임?
-
패스없는데 문해전 강의 안듣고 독학용으로 쓰는건 별로인가요?
-
매일 두세번은 쥐나네 시벌…
-
1시간 짜리 첫단원 하는데 2시간 30분 걸리는거 맞나? 그냥 듣는 것 뿐인데 이거...
-
멘탈관리법 1
여러분만의 멘탈관리법+정신건강유지법 공유해주세요..
-
마지막 일기 0
아마도 마지막 일기 어떻게 시작과 끝을 장식할까 그런거 신경쓰지 않고 길게 길게...
-
문학 인강 1
올오카 문학을 들었는데도 문학을 너무 못하고 문학은 김승리쌤이랑 안 맞는거 같아서...
-
얼버기 0
캬캬캬캬
-
부탁드려요 ~
-
[정오뉴스] 서울시는 오늘 오전 10시 35분 안전 안내문자를 발송해 "북한의...
-
성적인증 3
근데 평균 70정도에 표준편차 12~15면 나쁘지 않은 일반고인가요?
-
글은 잘못쓴다.. 레벨 어케올리냐
-
머가 맞는 지 모르겠어용ㅁ
-
문학이랑 선택은 어느정도 괜찮은데 독서는 그냥 순수 독해력 문제인거 같은데 어떻게 해결해야하나요?
-
이거왜이럼 러셀 1
이거 왜 로그인하면 외부생 이퀄모의고사 신청도 안돼요?
-
고1 정시 수학 1
현재 김기현 기생집 2,3점 풀고 있는데 앙이디어 기생집 4점 따라가는게 좋을까요?...
군대에서 코딩은 어떤 앱으로 하고 계신가요?