에라토스테네스의 체 C++ 구현 코드

에라토스테네스의 체 설명은 아래의 링크에 잘 되어있다.

에라토스네에스의 체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

아래의 코드로 구현 해보았다.

#include <algorithm>
using namespace std;

bool visit[1000001]; // 소수라면 false이다.(방문하지 않았으므로) <-> true
fill(visit,visit+1000001,false); // false로 초기화

for(int i=2;i<=n;i++)
{
	if(visit[i]==true) // 이미 true 판별난것은 배수들 true처리 되어있음.
		continue;
        
	for(int j=i*2;j<=n;j+=i) // i의 배수들 
		visit[j]=true;
}

 

일단 <algorithm>에서 지원하는 fill 함수를 통해 false로 초기화했다.

 

for문을  다 돌고난 뒤 결과적으로 visit의 i번째가 true 또는 false일텐데 아래의 뜻을 가진다.

• true : 소수가 아니다.
• false : 소수가 맞다.(방문하지 않았다.)

 

for(int j=i*2;j<=n;j+=i) // i의 배수들 
	visit[j]=true;

방문한 i번째의 배수들은 true로 처리한다.