오뇽

최대 공양수 gcm의 약자는 Greatest Common Measure

최소 공배수 lcm의 약자는 Least Common Multiple

#include <stdio.h>

int gcd( int a, int b );
int lcm( int a, int b );

int main( )
{
	int su1, su2;
	
	printf( "0을 입력하면 종료\n\n" );

	while( 1 )
	{
		printf( "두개의 정수 입력 : " );
		scanf( "%d%d", &su1, &su2 );
		if( su1 == 0 || su2 ==0 )	return 0;

		printf( "GCD( 최대공약수 ): %d\n", gcd( su1, su2 ) );
		printf( "LCM( 최소공배수 ): %d\n\n", lcm( su1, su2 ) );
	}
	
	return 0;
}

int gcd( int a, int b )
{
	if( a < b )
	{
		return gcd( b, a );
	}
	else if( a % b == 0 )
	{
		return b;
	}
	else
	{
		return gcd( b, a%b );
	}
}

int lcm( int a, int b )
{
	return a * b / gcd( a, b );
}

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

일반적인 방법으로 소수의 합을 구하는 코드인데, 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;
		}
	}
}

임의의 수를 입력하면 소수인지 판별해줌

#include <stdio.h>

int prime( int a );

int main( )
{
	int input;

	printf( "0을 입력하면 종료됩니다.\n\n" );

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

		if( prime(input) == 1 )	printf( "%d는(은) 소수 입니다.\n\n", input );
		if( prime(input) == 0 )	printf( "%d는(은) 소수가 아닙니다.\n\n", input );
	}

	return 0;
}

int prime( int a )
{
	int j;

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

	return 0;
}

1. 피보나치 수열이란.

2. 피보나치 수열이란.

MAX값을 조절해서 출력을 조절할 수 있음

//피보나치 수열
#define MAX 10

#include <stdio.h>

int main( )
{
	int i;
	int su1=1, su2=1, su3(0);
	int sum=2; 
	int arr[MAX]={ 1, 1, 0, };

	//연산
	for( i=2 ; i<MAX ; i++ )
	{
		su3 = su1 + su2;
		sum += su3;
		
		arr[i] = su3;

		su1 = su2;
		su2 = su3;
	}

	//출력
	for( i=0 ; i<MAX ; i++ )
	{
		printf("%d", arr[i]);
		
		if( i != MAX-1 )	printf(" + ");
		if( i == MAX-1 )	printf(" = %d\n\n", sum);
	}

	return 0;
}

재귀호출로 처리

#define _MAX 10

#include <stdio.h>

int factorial( int su );

int main( )
{
	int i, sum=0;

	for( i=1 ; i<=_MAX ; i++ )
	{
		sum += factorial( i );
	}

	printf( "%d\n", sum );

	return 0;
}

int factorial( int su )
{
	if( su == 1 )
	{
		return su;
	}

	else
	{
		return su *= factorial( su-1 );
	}
}

이번에는 과정도 출력하며 _MAX 값을 바꿔줌에 따라 나열되는 항의 갯수가 바뀜

#define _MAX 20

#include <stdio.h>

int main( )
{
	int i=0, j=1;
	int sum=0;
	int arr[ _MAX ];

	//계산
	for( i=0 ; i<_MAX ; i++ )
	{
		j = j + i ;
		sum = sum + j;

		arr[i] = j;
	}

	//출력
	for( i=0 ; i<_MAX ; i++ )
	{
		printf( "%d", arr[i] );

		if( i != _MAX-1 )	printf( " + " );
		if( i == _MAX-1 )	printf( " = %d\n\n", sum );
	}

	return 0;
}

#include <iostream>

const int nMax = 10;

int main( )
{
	bool bSitch = true;
	int sum = 1;

	for( int i=2 ; i<=nMax ; ++i )
	{
		if( bSitch == true )
		{
			sum += i;
		}
		else
		{
			sum -= i;
		}
		bSitch = !bSitch;
	}

	printf( "%d\n", sum );

	return 0;
}

#define	_NORMAL
#define	MAX 100

#include <stdio.h>

int main( )
{
	int i=0;
	int sum=0;

#ifdef _NORMAL
	for( i=1 ; i<=MAX ; i++ )
	{
		sum += i;
	}
#else
	sum = ( MAX+1 ) * ( MAX/2 );
#endif

	printf( "%d\n", sum );

	return 0;
}