컴공 일기 246
… 예… 오랜만에 들어와서 요새 풀고 있는 알고리즘 코드 하나 올려놓고 갑니다…
여전히 꽤…는 아니어도 열심히는 사는 중입니다…
간단한 해설을 하자면 소수를 찾는 알고리즘입니다.
주로 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를 선물하세요.
-
영어 사문이 그나마 든든하게 버텨주니까 부담이 좀 덜하네요 믿는 도끼에 발등 찍힐...
-
오른쪽 발목만 피부가 자꾸 쓸리고 까져서 ㅈㄴ 아픔.. 내가 뭐 신발 신고 운동을...
-
존밤되세요
-
슈퍼아이돌이면서 현역 정시로 인서울 대학 간 지헌 누나와 5시간 동안 스터디윗미
-
하아 도파민 과다분비 돼서 잠 못자고 여기까지 와버림
-
아니 어떻게 “다음주” 목요일이 수능이야
-
역대급 캐리판 ㄹㅇ
-
페이커 저 새끼 45세트에 한 것보다 더하라고? 오히려 슌 엘크가 45세트 뒤지게...
-
오늘 실모 보실거임?
-
월즈오면 LCK팀 응원할수밖에없음 ㅋㅋㅋㅋㅋ
-
근데님들 만약애 21월즈때 티원이 담원꺾고 올라갔으면 3
그때 EDG이겼을거같음?
-
4세트 엘크가 성장잘한거 집어던져서 5세트까지 간거고 5세트 빈 느낌없고 온 똥구멍...
-
공통 다 맞을 수 있겠다는 근자감이 드네 ㅋㅋㅋ 제발 25수능수학 공통1틀 미적...
-
ㅅㅅㅅ
-
7번이 진짜 딱 좋을듯
-
닉변완. 3
-
쓰리핏 탐나네 ㅋㅋ
-
ㅈㄴ 무서운데?
-
스킨 후보 10
ㅇㅇ
-
린킨파크 한번만 봐준다 ㅋㅋㅋ
-
-
아진짜못참겠네 4
헤으응
-
월즈 스킨 예측 6
우스우스: 그라가스 오 너는 최고야: 신짜오 신: 갈리오 or 아리 or 사일러스...
-
나만 그런거 아니지? 걍 지금 씻고 독서실이나 갈까..
-
수능은 티원처럼 7
수능날에 최고점 찍자고
-
캬
-
어 상혁이형이야 0
.
-
건국대 1
건국대 자전 추합 몇번까지 빠질 것 같나요??
-
-
뭐해? 1
올려
-
실모 풀었는데 둘다 3n점대 나와요...ㅎ ㅠㅠㅠ 수능때 2등급이라도 받고싶은데 걍...
-
아예 버려도 괜찮나요 ?? 이거 버리면 남은 문제는 다 맞아야 하는데 요즘 세포분열...
-
지들 졌다고 시위하는건가 추하네 좀 ㅋㅋㅋ
-
초딩 때부터 게임대회 관심 생겨서 응원했는데 16년 우승보다 지금이 더 기분 좋음...
-
4시드 미드 십캐리 결승 패승패승승
-
23년 3세트 징동한테 무난히 끌려가다가 질뻔한거 토스로 세계선 바꾸고 24년...
-
-
럭스한적있음??
-
아 개귀엽네ㅋㅋㅋ
-
1사람당 10만덕 댓글 ㄱㄱ혓!
-
대가리 깨러간다 뭐? 국제전 7년 무관? 뭐? 물로켓? 응 월즈리핏 ㅋㅋ
-
초중반 운영은 blg가 훨씬 잘한 것 같은데
-
아 몰라 대상혁 5회 우승 라이브로 봤잖아 한잔해 ㅋㅋㅋ
-
역2롤 t1 faker
-
이래도 까?
-
둘 덕분에 이겼다 ㄹㅇ
-
ㅅㅅㅅㅅㅅ
-
UP
-
시이이이발 대상혁 대상혁 대상혁
-
롤켜야지 0
달려
군대에서 코딩은 어떤 앱으로 하고 계신가요?