[정보처리기사] 소수의 합 - C언어 구현 - 에라토스테네스의 체를 이용한 소수의 합 구하기

1. 에라토스테네스의 체란

2. 에라토스테네스의 체란

에라토스테네스의 체를 이용한 문제는 프로젝트 오일러 사이트에 올라온 문제이기도 하며, 에라토스테네스의 체를 이용 안하고 풀었을 때와 이용 했을 때의 시간 차이는 엄청납니다. 위의 링크 중 위키피디아 내용을 참고해서 소스를 만들었고, 소수 목록을 파일로 출력하여 따로 볼 수 있게 만들었습니다.

 

파일 저장 경로는 C:\prime.txt 인데, 관리자 계정이 아니거나 UAC가 켜져 있으면 실행하다 오류가 저장이 안되는데, 그럴때는 C드라이브 말고 D드라이브 등으로 경로를 바꿔주고 하면 됩니다.

 

암튼 에라토스테네스의 체의 핵심은 소수를 찾는게 아니라 소수가 아닌 걸 체로 걸러내고 남은 걸 찾는것입니다.

 

#define MAX	2000000

#include <stdio.h>

int main( )
{
	bool	*PrimeArray = new bool[ MAX+1 ];
	double	sum=0;

	for( int i=2 ; i<=MAX ; i++ )
	{
		PrimeArray[i]=true;
	}

	//에라토스테네스의 체에 맞게 소수를 구함
	//만일, PrimeArray[i]가 true이면 i 이후의 i 배수는
	//약수로 i를 가지고 있는 것이 되므로 i 이후의 i 배수에 대해
	//false값을 준다.
	//PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시
	//소수가 아니게 된다. 그러므로 검사할 필요도 없다.
	for( int i=2 ; ( i*i )<=MAX ; i++ )
	{
		if( PrimeArray[i] == true )
		{
			for( int j=i+i ; j<=MAX ; j+=i )
			{
				PrimeArray[j] = false;
			}
		}
	}

	//MAX 범위 내의 소수의 합
	for( int i=2 ; i<=MAX ; i++ )
	{
		if( PrimeArray[i] == true )
		{
			sum += i;
		}
	}

	printf( "%.lf\n", sum );
	
	FILE    *pFile;
	pFile = fopen( "D:/prime.txt", "wt" ); 

	for( int i=2 ; i<=MAX ; i++ ) 
	{
		if( PrimeArray[i] == true ) 
		{ 
			fprintf( pFile, "%d\n", i );
		} 
	}

	if( pFile != NULL )
	{
		fclose( pFile );
	}

	//해제
	if( PrimeArray != NULL )
	{
		delete[] PrimeArray;
	}
}