컴공 일기 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를 선물하세요.
-
내용을 입력하세요.
-
오늘 한 것. 11:00 공부. 개념의 나비효과 문학파트를 내일 까지하면 마무리 될...
-
공통은 쉬운데 미적 존나게 어렵네
-
sky라는 대학이 따로 있는건줄 앎 ㅋㅋ 알고보니 서울대 연세대 고려대.. 나만...
-
언확쌍사인데 6모 백분위 99 91 2 99 99이고 서울대식으로 406.3...
-
국어 전체적으로 평균 3-4 왔다갔다하는 학생입니다 수시 끝나고 본격적으로 국어...
-
저만 그런가요 실모는 개쉽고 일반 문제가 훨씬어렵네요
-
라유 투자 은행 4
1, 10만덕 저축 연이율 5% 2, 투자한 덕코의 1.5% 만큼 라유가 복권 1등...
-
강대X 마니 어렵나요? 15
약간 더 27 감성이려나 칼캠이나 빡모, 해원이랑 비교했을 때 어떻던가요
-
지금부터 수학만 한다고 해도 높2가 한계일 것 같은데..
-
나만 4
사설컨이랑 평가원이랑 괴리감이 이렇게 큰가 평가원 수학 보면 그래도 공통에서...
-
2학기 수행평가 지금 먼저 한다는데 안내도 될까요?
-
S는 썩 기분 좋진 않을듯 S>>>>k,y 인데
-
언매가 어느정도 나와야하느요..!! 교차지원 생각도 있어요 과는 상관없고 연대에...
-
전자 버스타야함 후자 도보5분 님들이면 어디감
-
시냅스 너무 안풀리는데 12
뉴런을 계속 복습하는게 좋을까요? 수능 이제 얼마 안남았는데 이제 뉴런수1 끝냈어요...
-
나도 풀어보고싶어
-
김뭉먕 <<< goat
-
한수 페이지에 팔던게 할까마ㅏㄹ까 고민중인데 어떰?
-
경유야… 페이커가 우스워…?
-
공통을 잘하면 미적분도 잘한다 는 항상 성립하지 않으므로 거짓 미적분만 해야겠...
-
상위권 교차 이런걸로 문과도 영향 갈 수 있나요…? 물론 제가 최상위권 지망은...
-
닥후임??
-
어 ㅅㅂ 포에서 조금 바이럴 햇다가 너도나도 이매진 푸는 분위기 됨 ㅈ됨 나만 풀거였는데
-
갠적으로 강대x는 너무 어려웠어요…
-
저 같은 학생따가리 입장에선 문학 자작 문제가 비문학보다 만들기 쉬운듯
-
그대의 겨울이 너무나 춥더라도 너무 노여워 하지 않았으면 한다 기다리면, 아주...
-
수능 100일의 전사 드가자~ 2주만 더 놀고 공부해야지
-
현역이고ㅠ내친구 현강 듣는거같은데 숨기는 심리는 뭐임?
-
오래된 문젠데 계산은 그리 복잡하지 않았던 걸로 기억함 답은 있는데 해설이...
-
ㄱㅆㅈㅁㅌ 1
베이컨 치즈 라구비프 (일명 베치라) 다들 꼭먹어보세요 ㄹㅇ 존맛탱구리
-
천동설 ㄷㄷ
-
사문-개념3회독(불후의 명강,스피드버전,최적 스피드) 도표(엠스킬)2회독+ 기출...
-
꿀맛
-
뭐 어떻게 공부해야하죠 ㅅㅂ ㅈ됐다 규조토니 애추니 뭐니 모르겠는데
-
나이스 2
아직 수능 3번 더 볼수 있다 끼얏호우~~~
-
대성아니면 해설 잘되어있는 책으로 낮2 중3 왔다갔다함 피지컬n제 n제게임 4규s1...
-
김기현 아이디어에서 배우는것들 말고도 기출생각집이나 커넥션 같은 강의에서 새로 배우는거 많나요?
-
고영근 교수의 표준중세국어문법론으로 입문하면 좋습니다 다만 돈이 좀 아깝다면...
-
국어 연계 0
이매진 8호까지 문학만 풀고 강민철 이비에스 독서랑 앱스키마로 하면 연계충분할까요?...
-
똑바로 안읽어서 틀린 문제엔 주의할 점 + 정신차리라고 욕도 가끔 써놨는데...
-
이매진 0
이매진 8호까지 문학만 풀고 강민철 이비에스 독서랑 앱스키마로 하면 연계충분할까요?...
-
??
-
설거지 하고 있는 엄마 옆에 가서 엄마 나 국어 수학 합쳐서 X개 틀렸어 하니까...
-
아오
-
일반고고 전교과는 2.9에 수학만 전부 1이에요.. 종합 넣을때 이점이 있을까요..?
-
22에 비하면 진짜 많이 봐준 느낌이랄까
군대에서 코딩은 어떤 앱으로 하고 계신가요?