컴공 일기 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를 선물하세요.
-
오래된 문젠데 계산은 그리 복잡하지 않았던 걸로 기억함 답은 있는데 해설이...
-
천동설 ㄷㄷ
-
사문-개념3회독(불후의 명강,스피드버전,최적 스피드) 도표(엠스킬)2회독+ 기출...
-
꿀맛
-
뭐 어떻게 공부해야하죠 ㅅㅂ ㅈ됐다 규조토니 애추니 뭐니 모르겠는데
-
나이스 2
아직 수능 3번 더 볼수 있다 끼얏호우~~~
-
대성아니면 해설 잘되어있는 책으로 낮2 중3 왔다갔다함 피지컬n제 n제게임 4규s1...
-
김기현 아이디어에서 배우는것들 말고도 기출생각집이나 커넥션 같은 강의에서 새로 배우는거 많나요?
-
고영근 교수의 표준중세국어문법론으로 입문하면 좋습니다 다만 돈이 좀 아깝다면...
-
국어 연계 0
이매진 8호까지 문학만 풀고 강민철 이비에스 독서랑 앱스키마로 하면 연계충분할까요?...
-
똑바로 안읽어서 틀린 문제엔 주의할 점 + 정신차리라고 욕도 가끔 써놨는데...
-
이매진 0
이매진 8호까지 문학만 풀고 강민철 이비에스 독서랑 앱스키마로 하면 연계충분할까요?...
-
??
-
설거지 하고 있는 엄마 옆에 가서 엄마 나 국어 수학 합쳐서 X개 틀렸어 하니까...
-
아오
-
일반고고 전교과는 2.9에 수학만 전부 1이에요.. 종합 넣을때 이점이 있을까요..?
-
22에 비하면 진짜 많이 봐준 느낌이랄까
-
전역하고싶어 3
-
고 1
고
-
수학:96 영어:98 물리:46 지구:44 나름 자랑하는건데 씹갓들에 비하면... 부끄럽네요ㅜ
-
젠장 또 하니야 5
기습숭배
-
탕후루먹으러가자고하네요 마라탕후루가 진짜 있는 루트였구나
-
비추임?
-
금연 포기 0
두달 시도했는데 그냥 입시 끝나고 끊는게 맞는듯 ㅋㅋ
-
언니 장수생인데 아빠가 대학붙고 바로 공무원시험준비 하라니까 7
어제 싸우고 오늘도 계속 울던데 아빠가 잘못한건 아니지않나요? 성적도 어느정도 잘...
-
흠흠...
-
강남대성학원 재수종합반, 두각학원 단과 출강하시며 강남대성수능연구소에 계신...
-
1배속하면 말이 너무 느림. 현강 들을땐 안어색한거보면 인강으로 올릴 때 자체...
-
그래? 알앤디 한번 삭감했더니 문과가 살아나네!
-
다들 성적상승 1
계단식으로 오른다는걸 언제 어떻게 느껴보셨나요?
-
이매진 0
이매진이 연계 전작품 다있다는데 이거 8호까지 다풀고 복습하면 연계 충분한가요?
-
번호딸까
-
시기상 다들 힘 빠지고 의욕을 잃어갈 듯합니다... 다들 8월까지만 버티면...
-
문제에서 ㄱ보기가 옳다고 되어있는데 사내 동호회는 공식조직이 아니고 자발적 결사체...
-
지구에서 움직이는 우주선의 시간을 측정랄 때 지구의 시간은 지연된 시간이고 우주선의...
-
수특에 이렇게 나와있는데 그래서 답이 왜 3번인 거죠? 맨틀 위에 떠 있는 지각이래매...
-
지금까지 정부 스탠스상 진짜 당장 목에 칼 안들어오면 무조건 시간 끌거라고 봄...
-
소요 시간 72분 93점(독서 -5 문학 -2) 난이도는 6모랑 대비해서 독서는...
-
요새 강남 대치 부모님들 수능 성적표 달라고함? 과외힐때 3
보현사건땜에 달라하나? 이제
-
상남자 특 3
듄 연계공부 안함
-
문학 << 불 언매 << 불 비문학 << 가나형에 난이도 몰빵이 메타인건가 다 그런 느낌이네
-
파일 받아서 풀어봤는데 62점 나왔어요 교육청, 평가원에서는 대부분 2등급 받았어요...
-
잇올같은데 10월말 11월초에 3주정도 등록가능한가요..? 0
혹시 저때 등록해보신분 계신가요..?
-
몇 개 정도 푸시나요? 지금 구매한 게(상상, 이감, 김승모) 35~6회 정돈데 더...
-
아
-
스카 너무추워서 5
알래스카온줄 하하하
-
그래도 8시간은 했네..
-
굿
-
어려운 27번 정도임?
군대에서 코딩은 어떤 앱으로 하고 계신가요?