컴공 일기 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를 선물하세요.
-
전건과 후건이 모두 참이라서 명제가 참 둘사이에 인과관계는 없다고 함 하지만...
-
?
-
할루 4
-
블랙홀때문에 우주팽창이 이루어진다는 말을 어디서 들어봤음
-
가기전에 하나만 0
히카 시즌4 왤캐 낯설지 문제들이 쉽지 않네 음,,, ㅅㅂ 칸타타형 살살내라고
-
계속 튀어나오는 1q 킬러들 제끼면서 500원씩 쓰고 있다 보면 진짜 진한 현타에...
-
고2학평 에피 4
보통 전체에서 3-4개틀까진 뜨죠?
-
ㅇㅂㄱ 8
10모 잘보고 올게요
-
축약은 음운개수 줄어드는 반면 교체는 안 줄자나요? 굳이-------- 이건...
-
일어나고 나서 6시간 정도는 지나야 머리가 돌아가서 수능패턴 맞추려고 맨날 새벽...
-
애들한테 다 그러시는 스타일인데 한번씩 계속 스몰토크하려고 말 걸고 자습할때...
-
힘이 안나네요 1
오늘은 갓생하려했는데 집나간 패턴이 안돌아와요
-
얼버기 14
-
17시즌 9등 -> 현역 18수능 조지고 재수 18시즌 5등하고 승차 없는 6등...
-
미국에서도 오르비 하시는 분들이 많나
-
시험 6일 남았네 시발
-
한시간에 한마디 할까 말까 용건만 간단히 전하는 입무겁고 합리적인 이성친구
-
수학황분들 0
이미지 모고 vs 빡모 ㅊㅊ점요
-
ㅈ됐다 1
내일 10몬데, 실모 오답하느라 아직까지 깨어있다 ㄷㄷ
-
뒷자리 오버워치하네 15
십 스터디카페가 피방이 됐네
-
홍익대 경영 항공대 항공교통물류 둘다 작년기준 최초합권입니다.
-
오후9시에일어나도아무문제없는게아닐까
-
과탐 둘다 안하긴 하지만 생명은 비유전까지는 피지컬로 풀수 잇어서 유전 찍맞 2...
-
마지막 수능이 코로나 한창일때 한참 옛날인데 지금도 수능만 다가오면 싱숭생숭함 이것도 병인듯
-
아 보면 짜증나고 안보이면 보고싶고 수능같은 녀석 나도 자야되는데
-
마지막 ㅇㅈ 8
수능 끝나고 유럽 쫙 돌았는데 베를린 한번 더 가고 싶다
-
모두 수능 대박을 기원하며. 우리는 제법 머리가 좋다 너의 fame. 나의 자랑...
-
아 자야되는데 ㅅㅂ 15
언제자냐고 ㅠㅡㅠ 잠이 안 와
-
마피아42
-
한달간 닫는다.
-
진짜 ㅇㅈ 4
아.
-
피자 최고
-
연애하는 꿈 자주꿈 그리고 일어나서 설렘
-
영어 공부특 4
미룸 그러다가 수능 2뜨고 메디컬 안 되니까 후회함
-
진짜 안좋은데 노트북으로 해야겠다
-
자기엔 늦었다 4
걍 밤새고 카페인 빨아야지 일단 컵라면 먹고싶은데 추천바듬
-
고전소설 7
다들 어떻게 푸시나요
-
중독되겠네 한달뒤에 올게 빠이
-
안경 이것저것 ㅇ?ㅈ 12
얼빡 다 가져온듯 흑역사 박제느낌인거지
-
도파민 나와서 못 끊겠네 어떻게 쉬고 있었던 오르빈데
-
야스 인증 4
야스장와서 야스하는 사진 ㅇㅈ 데드 160. 스펙 175 68
-
성적은 계속 안 나오고 수능은 한 달도 채 남지 않았고… +1 거의 확정인데 끝까지...
-
계정은 남겨둘텐데 이제 다시는 안올게요 적어도 몇달은..
-
님들 빨리 자여 3
내일 10모인가?? 물론 전 현역이 아니라 안보기는 한데..
군대에서 코딩은 어떤 앱으로 하고 계신가요?