컴공 일기 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를 선물하세요.
-
오늘 지출 7
증사 마넌 버스비 삼처넌 원서비 사만이처넌 계:오만오처넌 아.
-
사탐해도 제한 없었으면 제가 했을 조합
-
런도 런 나름이지 이상한 곳으로 도주하시면 안됩니다 9
예를 들어 경제나 세계사로 도주를 하시게 되면 끔찍한 사태가 발생할 수도 있습니다..
-
여친 고딩동창이 여친한테 연애중인거 아는데도 불구하고 둘이서 영화보자고 플러팅해서...
-
난 경고했다
-
https://www.youtube.com/watch?v=ZRebVq_TseY
-
이 중 적지 않은 수가 본인들은 콩고 가서 사탐원주민 학살하는 레오폴드 2세가...
-
어어 화내지 말고 긁히지 말고 나도 화1하는데 솔직히 사탐 개노잼이고 화1...
-
어디가 젤좋음,,,?
-
4고 시즌1 수1 푸는 중입니다. 1권에 3일씩 총 10일정도 잡아두고 수1 수2...
-
내가 봤을 때는 사탐런 자체로 욕먹는 거라기 보다는 글의 태도에서 의도가 보여서임....
-
사장님이 박스살짝 열어보고 원하는거 주셧음...
-
1. 굉장히 착하고 귀욤귀욤하거나 2. 어딘가 나사가 한 열개쯤 빠져있거나 둘 중 하나 같다
-
윤하 '사건의 지평선', 고등 교과서에 실린다…문학 지문 수록 8
가수 윤하의 히트곡 '사건의 지평선'이 고등 교과서에 실린다. 6일 소속사...
-
사탐런 소신발언 8
본인포함 사탐런한사람들은 진작에 수능끝나고 각재고있었거나 진짜 늦어도 6모에는...
-
사문 14번 2
특정 세대가 원래 단어에 새로운 의미를 부여하여 그들끼리 사용하는 것 ㅡ>...
-
전반적 상황: 정시로는 오직 서울대 목표고, 수리논술은 약대위주로 쓰려합니다....
-
정치와법 ox 8
미성년자가 자신의 용돈으로 구매한 물건을, 타인에게 무상으로 증여할 때에는 법정...
-
과외학생이 6~7등급인데 듣게 해도 되나욧?
-
3 4 최저러나 의치표본 둘다 원보다는 비교우위 가져감?
-
이게 정법이 궤도에 한번 오르면 우화등선 가능함
-
사탐런해서 이득볼지 손해볼지는 본인의 현재 국수성적이 말해주는거임 무조건 이득...
-
동의하면 개1추
-
사탐런결론) 3
과탐선택하고국영수로최저맞춰서수시로대학가기
-
걍 투과목 소수 빼면 타격없지않음?ㅇㅅㅇ
-
뭐가 젤 좋을까요 국어goat형님들..
-
독재하기도 하고 뱔로 찾아보는게 성적 뭣같이 나와도 귀찮아서 하던거 하는 편이라...
-
단어 숫자 조합으로 아이디 새로 만들라고 하는데 숫자 선택 고민이에요 보기에 더...
-
개당 킬러주제 2 3문제씩 더 내서 1컷 40으로 찍기싸움하자니까? 모두가 희망을...
-
흠냐뇨이..... 모교가기 싫어요
-
고민이네요.
-
수능 접수 완료 6
이러면 오르비 1년 더해도 되겠죠? team. 정법 물2 화이팅
-
파이널2만 샀음 외에는 아수라 들을 예정
-
순정남들만 웃는 그런 수능을 바란다
-
N제를 풀고자하는디 너무 재미없어보인다.... 아....
-
롤스의 무지의 베일이라는게 정말 똑똑한 개념이 아닌가 14
이 오르비에서 매일매일 벌어지는 논쟁과 떡밥들 모두 우리가 우리의 지위와 계층,...
-
추천하고픈 문제집 있으실까요..?
-
아니 설의 간 우리 고등학교 선배 수능 접수했는데? 7
아니 이게 뭔.. 대체 무슨 생각이십니까 누님.. ㅋㅋㅋㅋㅋ
-
패로인을 볼까 러시부끄를 볼까 작화는 후자긴 한데 스토리는 전자가 나을거 같기두 하고
-
6모 이후로도 과목 바꾸는건 비추하는데, 하물며 9모 이후에 과목 바꿀까 고민하는거...
-
반영비 레전드네 걍 과탐 가산땜에그런가
-
음...
-
이번 9모에서 70점대 맞고 5등급 떴는데 기출 문제집 추천해주세요 ㅠㅠㅠㅠㅠㅠ!!...
-
45점나왔어요 조금 아리까리하게 풀긴했는데... 남은 시간동안 만점 만들수있을까요...?
-
사문 임정환 vs윤성훈 생윤 임정환 vs 김종익 짧은 근거와 함께 추천주십쇼
-
세계사 정법 12월까지 수특으로 독학 인강 26버전 업로드되면 그걸로 공부 ㅇㄸ
-
연대 기준으로 작년에 사탐 백분위 99 = 과탐 백분위 96인데 문제는 올해 상황상...
-
ㅠㅠ 16
화이팅
-
예를들어 내신 BB면 CC에 비해 설대식 몇점정도 이득이라던지
-
으악 ㅅ1ㅂ 소리부터 나오던데 걍 현기증남
군대에서 코딩은 어떤 앱으로 하고 계신가요?