컴공 일기 246
게시글 주소: https://iu.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
45. 의 A와 B에 들어갈 수 있는 말을 에서 모두 고르면? 양자 구슬 한 쌍을...
-
국어 일클 4주차 예습 영어 막장구원 11~12강 공부흔적 11~12일차 스피드보카...
-
이번주학습통계 수요일은 오류로 종료시각이 2330인데 기록안대잇네욤 담주 월부턴...
-
5월부터 수학 시작해서 세젤쉬 다 듣고 미친기분 시작편 2회독하고 미친개념...
-
성대 자연계 5
지금 생각하니 논술로 어케 뚫었지 겁나 아득하네
-
내년 시험목표로 올해 미리 기출강좌(올오카)수강하려 하는데 올오카 수강하면서...
-
혹시나 최집시간 오류로 품타방 강퇴되신분은 쪽지주세요 가입제한 풀어뒀어용
-
서울예고가 마즘?
-
어차피 연계 0
여러분이 중요하다고 생각한 거 평가원이 피해서 냄. 그러니 꼼꼼히 봐요
-
문학 화작 말고 수업 안 듣는데 다니는게 의미가 있나요
-
제발 마음껏 주장해주세요 저만 공부하게
-
진짜 망햇어
-
7월 0
개빨리 지나가네
-
욕하기 0
쒸르바아아아아아아ㅏ아아아아아아아아아아아알
-
완벽하지 않게 쌓아도, 100% 쌓지않아도 상관없음. 다만, 잘못 쌓는게 문제임
-
강으냥 먼가 어색하누
-
와...
-
만들어지면 좋을 듯
-
장풍샘등장
-
미적>>> 수2>수1 인걸 느낌 가형 아녀서 다행이다
-
논술 준비 해보신 분들... 과외랑 학원 중에 고민하고 있는데 어떤 게 좀 더...
-
근사계산 3
1번계산이랑 2번계산이 왜값이다른가요?
-
난 수학에서 ~~의 개수, 가능한 ~~값의 합 이게 너무 싫어 1
풀어도 깔끔하지가 않고 놓친거있나 찝찝한것들
-
메가에서 수특 독서 다루는 강의는 강e분 밖에 없냐 1
다 죄다 문학만 하네 ㅋ
-
개굿
-
얼마나 박아야될까 하..일단 독해하는데 시간이 좀? 오래 걸리는듯 시간이 아슬아슬할때가 많음
-
이게 좋다고 말해야할지 모르겠음 그냥 쉬워서 좋다고 착각하는건가 산지 얼마안돼서...
-
시불막지마
-
수1 질문 5
양변에 g(x) 나눠버리는거 왜 안되나여 ㅇㅅㅇ
-
현역 최저러고 시대 서바 모고 국어랑 수학 2개 다니고 있는데 둘 다 1?...은...
-
유당불내증 장점 7
변비 걸렸을때 라떼 350ml만 마셔주면 바로 쾌변
-
윤사 해봤는데 1
생윤하면 모래주머니 효과 남? 내신 윤사한다고 자이스토리를 벅벅 풀고 암기한 전적있음
-
그저 평범해지기 위해서 엄청난 에너지를 쓰는 사람들이 있다는 것을 아무도 알지...
-
불행한지도 모름 행복했을 때와 대조되어서 현실이 불행하다고 느끼는 건데 평생을...
-
100일의전사대기중.
-
영어 0
지금 2년째 유기중이고 작수(모의) 84 6모 77…입니다 수능까지 강사컨 딱...
-
낮에는 해커스 강남에서 토플이랑 hsk타고 밤에는 놀러다니고 재밌을듯 그리고 3월부터 다시 자취
-
헉 똥테 달성 6
감사합니다~
-
헉 0
반갑꼬리
-
안정 3이 목표고 7모 낮은 2등급입니다 이 세개 외에 더 좋은 엔제 있으면 추천 부탁드랴용
-
드릴 이미 끝냈는데 엄
-
N수행열차 미리 탑승합니다
-
집중 너무 못하네 요즘
-
대학 '전자책 구독' 추진…전공책 불법복제 막는다 23
[서울경제] 대학가에서 전공서적을 불법 복제하는 관행이 판을 치자 대학들이 전자책...
군대에서 코딩은 어떤 앱으로 하고 계신가요?