오뇽

#include <stdio.h>

#define MAX 10

int main()
{
	int arr[MAX];
	int i, j=1;
	int HIGH, LOW, MID;

	//배열 공간 초기화
	for(i=0 ; i<MAX ; i++)
	{
		arr[i] = j;
		j += 2;
	} 

	printf("0을 입력하면 종료");
	
	while(1)
	{
		bool state(1);
		int key;

		LOW = 0;
		HIGH = MAX;
		MID = (LOW+HIGH)/2;

		//배열 공간의 내용을 보여줌
		for(i=0 ; i<MAX ; i++)
		{
			printf("%2d번지 : %2d\n", i+1, arr[i]);
		}

		//키 값을 입력
		printf("\nkey값을 입력하세요 : ");
		scanf("%d", &key);
		if(key <= 0) return 0;

		//2진 검색
		while(state == 1)
		{
			MID = (LOW+HIGH)/2;

			if(arr[MID] == key)
			{
				printf("%d번지에 있습니다.\n\n", MID+1);
				state = 0;
			}
			if(key < arr[MID])
			{
				if(arr[MAX-1]<key)	
					state = 0;

				HIGH = MID-1;
			}
			if(key > arr[MID])
			{
				LOW = MID+1;
			}
		}
		//printf("값이 없습니다.");
	}

	return 0;
}

#include <stdio.h>

void insertion_sort( int *nArr, int nCount )
{
	int i(0), j(0);
	int key = 0;

	for( i=1 ; i<nCount ; ++i )
	{
		key=nArr[i];
		for( j=i-1 ; j>=0 ; --j )
		{
			if( nArr[j]>key )
			{
				nArr[j+1] = nArr[j];
			}
			else
			{
				break;
			}
		}
		nArr[j+1] = key;
	}
	int a = 9;
}

int main( )
{
	int nArr[] = { 7, 3, 8, 0, 2, 1, 5, 13, 6 };
	int nCount = sizeof(nArr)/sizeof(*nArr);
	
	insertion_sort( nArr, nCount );

	for( int i=0 ; i<nCount ; ++i )
	{
		printf( "%d\n", nArr[i] );
	}

	return 0;
}

#include <stdio.h>

#define MAX 10

int main()
{
	int arr[MAX];
	int i, j;
	int temp;

	printf("음수를 입력하면 종료\n\n");
	
	while(1)
	{
		//입력
		for(i=0 ; i<MAX ; i++)
		{
			printf("%d번지 수를 입력하세요 : ", i+1);
			scanf("%d", &arr[i]);
			if(arr[i] < 0)	return 0;
		}

		//입력 확인
		printf("\n입력한 수는 ");
		for(i=0 ; i<MAX ; i++)
		{
			printf("%2d ", arr[i]);
		}
		printf("\n");

		//정렬
		for(i=0 ; i<MAX-1 ; i++)
		{
			for(j=0 ; j<MAX-(i+1) ; j++)
			{
				//꺽쇠 방향만 바꾸면 오름, 내름
				if(arr[j] > arr[j+1])
				{
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}//for j
		}//for i

		//출력
		printf("정렬된 수는 ");
		for(i=0 ; i<MAX ; i++)
			printf("%2d ", arr[i]);

		printf("\n\n");

	}//while(1)

	return 0;
}

#include <stdio.h>

#define MAX 5

int main()
{
	int arr[MAX];
	int i(0);
	int inputNum, min(99999999);
	int d, k(0);

	//입력 부분
	for(i=0 ; i<MAX ; i++)
	{
		printf("%2d번째 수를 입력 : ", i+1);
		scanf("%d", &arr[i]);
	}

	printf("\n입력한 수는 ");
	for(i=0 ; i<MAX ; i++)	printf("%d ", arr[i]);

	//특정 수 입력
	printf("\n\n임의수 입력 : ");
	scanf("%d", &inputNum);


	//검사
	for( i=0 ; i<MAX ; i++)
	{
		if(arr[i] > inputNum)
		{
			d=arr[i]-inputNum;
		}

		if(arr[i] < inputNum)
		{
			d=inputNum-arr[i];
		}

		if(d<min)	
		{
			min = d;
			k = arr[i];
		}
	}

	printf("가장 가까운 수는 : %d\n", k);

	return 0;
}

//배수의 수와 합을 구함
#include <stdio.h>

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

	while(1)
	{
		int sum(0), cnt(0), i;
		int MUL, MAX;

		printf("구하려는 배수를 입력 : ");
		scanf("%d", &MUL);

		printf("몇까지 구할거임? : ");
		scanf("%d", &MAX);

		//0을 입력하면 종료
		if(MUL == 0 || MAX == 0)
		{
			printf("0을 입력하여 종료함");
			return 0;
		}

		//MAX 값이 구하려는 배수보다 크면 실행
		if(MAX > MUL)
		{
			for( i=1 ; i<=MAX ; i++ )
			{
				if(i%MUL==0)
				{
					sum += i;
					++cnt;
				}//if
			}//for
			printf("\n%d까지의 %d의 배수의 합은 %d이며, 개수는 %d입니다.\n", MAX, MUL, sum, cnt);
		}//if

		//배수가 MAX보다 크면 다시
		if(MUL > MAX)
		{
			printf("ㅡㅡ");
		}

		printf("\n\n\n");
	}
	return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int nInput;

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

	while(1)
	{
		vector<int> vectorArr;

		printf("정수를 입력하세요 : ");
		scanf("%d", &nInput);
		if(nInput == 0)
		{
			return 0;
		}

		//약수 구하는 부분, 입력 값에서 /2 하므로써 효율적으로 변함.
		for( int i=1 ; i<=nInput/2 ; ++i )
		{
			//나누어 나머지가 0이면 약수
			if(nInput%i == 0)
			{
				vectorArr.push_back( i );
			}
		}

		//출력
		printf("입력한 수의 약수는 ");

		for( int j=0 ; j<vectorArr.size() ; ++j )
		{
			printf( "%d ", vectorArr[j] );
		}

		printf( "%d 이며, 총 %d개 입니다.\n\n", nInput, vectorArr.size()+1 );
	}

	return 0;
}

0을 입력할 때까지 소인수를 구함.

#include <stdio.h>

int main( )
{
	int i, j;
	int input, origin;
	int arr[100];

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

	while( 1 )
	{
		printf( "수를 입력하세요 : " );
		scanf( "%d", &input );
		if( input <= 0 )	return 0;

		origin = input;

		i = 2;
		j = 0;

		//수인수분해 부분
		while( input>1 )
		{
			if( input%i == 0 )
			{
				input = input/i;
				arr[j] = i;
				++j;
			}			
			if( input%i != 0 )	i++;			
		}

		//출력
		if( origin != 1 )
		{
			printf( "소인수분해 결과 : " );

			for( i=0 ; i<j ; i++ )
			{
				printf( "%d", arr[i] );			
				if( i<j-1 )		printf( " x " );
				if( j-1 == i )	printf( " = %d", origin );
			}
		}
		if( origin==1 )	printf( "2이상을 입력" );

		printf( "\n\n" );
	}

	return 0;
}

최대 공양수 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;
		}
	}
}