[정보처리기사] 소수의 합 - C언어 구현

일반적인 방법으로 소수의 합을 구하는 코드인데, 100만이나 200만 범위 내의 소수의 합을 구하려면 너무 느려요 ㅠㅠ 큰 범위 내의 소수의 합을 빠르게 구하고 싶으면 에라토스테네스의 체를 이용하면 됩니다.

//1부터 입력한 수까지 소수의 합
#include <stdio.h>

int prime( int a );

int main( )
{
	int input;
	int i;
	int sum;

	printf( "0을 입력하면 종료\n\n" );

	while(1)
	{
		sum = 0;

		//입력
		printf("양의 정수를 입력 : ");
		scanf( "%d", &input );
		if( input==0 )		return 0;

		//입력한 수까지 반복하고, 소수가 리턴되면서 누적
		for( i=2 ; i<=input ; i++ )
		{
			sum+=prime( i );
		}

		printf( "%d까지의 소수의 합 : %d\n\n\n", input,  sum );
	}

	return 0;
}

//소수를 구하는 함수
int prime( int a )
{
	int j;

	for(j=2 ; j<=a ; j++)
	{
		if(a%j == 0)
		{
			if(a == j) return a;
			if(a != j) return 0;
		}
	}
}