컴공 일기 246
게시글 주소: https://o.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마더텅이랑 둘 중 뭐살지 고민인데,,
-
확통 2컷 목표라서 공통에서 15 22 같은 킬러제외한 9 10 11 12 13...
-
EBSi on
-
러셀 신성규T 0
이번 윈터때 러셀 신성규쌤 수업 들으려 하는데요 수1, 수2 쎈발점 + 수분감...
-
고정 2등급이고 가끔 1등급으로 왔다갔다 합니다. 지금 이명학쌤 알고리즘이랑 리앤로...
-
ㄱㅏ보자 가보자 1
편입 합니다…
-
모집정지되면 1
입결 쭈우우우우욱밀려서 진짜 좃댐 안돼
-
수학 3 0
현재 김기현 T커리 타고있고 6,9모 둘다 수학 4인데 목표는 3입니다. 아직...
-
모집정지는 안 된다
-
7번 아닌데 답지엔 맞다고 되어있네요
-
점심은 또 먹었는데...ㅋㅎㅎㅎ 간식먹어야징
-
와 모집정지되나여
-
아 전공 어렵다 2
이게 뭔소리지
-
질문 ㅠㅠ 1
두문제가 안풀려요 ㅠ
-
이것좀 풀어주실 분 감사해요
-
내신 점수가 다들 어케되심
-
1. 국사 내신 시험 때 잠이 안 옴 그래서 걍 가방에 있던 주키마 꺼내서 풂 문학...
-
2사에 와서 입근 언제했냐해서 확인받았는데 1시간째 안보내주늩데
-
고2 정파 11모(10.15) 범위 맞춰서 공부해야할까요 4
고2 정시파이터입니다 수2 뉴런 미분부분 조금이랑 적분 들으면 완강인데 이번 11모...
-
옥린몽 관동별곡 정을선전 조웅전 이런거 안나와
-
영어공부어케함..?2뜰려면 지금 3임 삼년째 수능 13
어떻게보든 3이고 영어 공부 해본적없음 올해는 중앙대논술 최저땜에 해야할거같은데...
-
ㅇㅇ
-
19 수능 백분위 100 이엇는데 3문제인가 틀렷던거 같음 독서는 다 맞앗고 사실...
-
첫차 아니면 가망없
-
장자 / 하이데거의 공간론 태양 다이나모 가설 이거 두개 수특수완에서 본 기억이 안나느넫....
-
지금도 대성 라인업 보면 후덜덜한데, 여기에 김범준이 가세하고,,,, 그럼에도...
-
미국 - 뉴욕(x) 디씨(o) <- 이건 너무 유명한 오개념이라 잘 아는데 호주...
-
83 독서론 1틀 독서 2틀 문학 4틀 생각보단 ㅈ박진 않았네
-
ㅈㄱㄴ
-
화상과외인데 미소녀 AI버튜버 방송하는거처럼 미소녀 띄워놓고 목소리도 바꿔서 과외하는거임
-
되게 직설적인 표현이긴 한데 맞는 말인 것 같음 안정적인 걸 추구하다보니 역설적으로...
-
남은기간 영어 0
한문제 차이로 2,3등급 진동을 해서 안정 2를 맞추는 것을 목표로 하고...
-
다른 과목은 2~3등급에 영어는 1까지도 뜨는데 수학만 4~5등급 수학 딱...
-
제가 시간이 없었어서 검토를 못햇어요ㅠㅠ 집에와서 채점해봣는데 97점이라 실수했으면...
-
어떻게 타야할까여..?ㅠ 일단 수학은 이번달 안에 수1 수2 개념은 부족한데 냅다...
-
2111 2309 2311 2409 2411 2509 풀어봤는데 괜찮은 회차 또 있나
-
채점하지말고 무지성 동그라미 치자 양심상 1,2개는 틀린거로 하고.. 답지는...
-
러셀 바자관은 거의 준재종이고 사실상
-
공부 장소 공부 방법 등등
-
이제 풀고있는 n제 다 풀었고 강x랑 서킷x가 쌓여가서 이거 풀려고 하거든요 근데...
-
1% 알파메일 2
-
매기기 두렵네 유기할까 ㅋㅋㅋ
-
「きっと100年後の私は 분명 100년 후의 나는 美少女に生まれ変わってるはずだからさ...
-
열품타 홍보글 1
https://link.yeolpumta.com/P3R5cGU9Z3JvdXBJbnZp...
-
오류 있을시 바로 알려주시면 감사하겠습니다! 풀이과정도 같이 부탁드립니다!
-
현역정시러였던분들 27
고2 정시러인데 자꾸 정시 하는 사람한테 현역은어렵다구 그래서 심리적으로 계속 너무...
-
ㅈㄱㄴ 언매 미적 영 사문 지1 이고 내신 cc입니다..
군대에서 코딩은 어떤 앱으로 하고 계신가요?