오뇽

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;
	}
}