소인수분해 프로그램

//c 라이브러리 입니다.
//입출력에관한 유용한 함수들이 있습니다.
#include <stdio.h>
 
//소수를 저장하는 배열의 크기를 정합니다
#define SIZE 1000
 
//함수의 전방선언일까요 구현은 아래서 하겠습니다
//int 는 소수의 총갯수를 리턴하도록 했습니다
unsigned int Factorize(int Target, int* arrPrime);
 
//리턴값은 void로 해줬습니다
//성공의 실패유무를 알수있도록 리턴값을 정해주는것도 좋을것 같습니다.
unsigned int PrimeFactorize(int* arrPrime, unsigned int index, int Target, int* arrPrimeUsed);
 
//메인함수 입니다.
//소인수분해에 관한 프로그램을 작성해 보겠습니다.
int main()
{
    //첫째로 소인수분해 당할 변수가 필요하다고 생각합니다
    //소인수분해 당할 변수는 양수도되고 음수도 될꺼같네요
    //부호있는 int로 선언해주겠습니다
    int iTarget = 0;
 
    //타겟의 소수 를 저장하는 배열을 만들겠습니다
    int arrPrime[SIZE] = {0};
    //소수의 갯수를 기억하는 변수를 만들겠습니다
    //배열의 인덱스는 음수가 될수 없으므로 부호없는 정수를 선언 하겠습니다.
    unsigned int iIndex = 0u;
 
    //소인수분해에 사용된 소수들을 저장할 배열을 만들어 주겠습니다.
    int arrPrimeUsed[SIZE] = { 0 };
    unsigned int iPrimeIndex = 0u;
 
    //사용자에게 소인수분해할 숫자를 알아내기위해 질문을 출력합니다.
    printf("소인수분해할 숫자를 입력해주세요.\n");
    //정수를 입력받습니다.
    scanf_s("%d", &iTarget);
 
    //입력받은 값에 모든 소수를 찾아냅니다.
    iIndex = Factorize(iTarget, arrPrime);
    
    //소수의 갯수를 출력합니다
    printf("%d의소수의 갯수 : %u \n", iTarget, iIndex);
 
    //모든 소수들을 출력합니다
    for (unsigned int i = 0; i < iIndex; ++i)
    {
        printf("%u. Prine Number : %d\n", i + 1, arrPrime[i]);
    }
    
    //소인수 분해를 시작합니다
    //이 함수는 소수의 배열과 그 크기를 인자로 받습니다
    //검사받을 숫자도 인자로 받습니다.
    //사용된 소인수분해를 저장할 배열을 인자로 넘겨줍니다
    iPrimeIndex = PrimeFactorize(arrPrime, iIndex, iTarget, arrPrimeUsed);
    printf("소인수 분해에 사용된 소수의 갯수 : %d\n", iPrimeIndex);
    
    //소인수분해 출력부분
    for (unsigned int i = 0; i < iPrimeIndex; ++i)
    {
        //소수들을 출력하다가 가장 마지막 에서는 X를 출력 안합니다.
        printf("%d", arrPrimeUsed[i]);
        if (i < iPrimeIndex - 1)
            printf(" X ");
    }
 
    return 0;
} // 메인함수의 종료
 
//소수의 갯수를 검사할 함수의 구현부 입니다.
unsigned int Factorize(int Target, int* arrPrime)
{
    //검사받을 숫자를 저장할 변수를 선언해 줬습니다.
    int iTarget = Target;
    //배열의 주소를 저장할 포인터 입니다.
    int* Prime = arrPrime;
 
    //일단 기본적 검사 시작값은 5부터 하고
    //소수 2와 3은 초기값으로 저장해 두겠습니다.
    int Starting = 5;
    Prime[0] = 2;
    Prime[1] = 3;
 
    //배열의 인덱스를 기억해두는 변수입니다
    //현재 배열의 크기를
    unsigned int iIndex = 2u;
    //소수의 갯수를 셀 변수를 선언해줬습니다.
    unsigned int iCount = 0u;
    
    //배열이 다찰때까지 검사를 반복합니다.
    while (iIndex < SIZE && Starting <= iTarget)
    {
        //각각의 소수들을 숫자에 하나씩 나눈후
        //0이 한개도 안나올시 소수로 결정합니다
        for (unsigned int i = 0; i < iIndex; ++i)
        {
            //나머지가 0이 아닐경우 Count 올려줍니다
            if (Starting %Prime[i] != 0)
                ++iCount;
            //한번이라도 나머지가 0이 나오면 검사를 탈출합니다
            else
                break;
        }
 
        //만약 나머지가 0이 아닌 경우의 카운트가 현재인덱스의 크기랑 같다면
        // 그수는 소수이므로 배열에 추가해주겠습니다.
        if (iCount == iIndex)
        {            
            Prime[iIndex] = Starting;
            ++iIndex;
        }
 
        //새로운 검사를 시작하기전에 카운트를 0으로 초기화 시켜주고
        //다음 검사당할 숫자를 2증가시켜줍니다
        //짝수는 검사할필요없습니다 홀수에서 2씩 계속 증가시켜줍니다.
        iCount = 0;
        Starting += 2;
    } 
 
    return iIndex;
}
 
unsigned int PrimeFactorize(int * arrPrime, unsigned int index, int Target, int* arrPrimeUsed)
{
    //매개변수들을 따로 저장할 변수들을 선언해주겠습니다
    unsigned int iIndex = index;
    int iTarget = Target;
    int* Prime = arrPrime;
    int* PrimeUsed = arrPrimeUsed;
 
    //PrimeUsed의 배열의 크기를 저장할 변수를 선언하겠습니다.
    unsigned int iCurrentIndex = 0;
 
    //가장큰 소수부터 차례대로 나누기를 시작하겠습니다.
    //나머지가 0 일경우 소인수배열에 저장합니다
    for (unsigned int i = iIndex; i > 0;)
    {
        //나머지가 0 일경우 iTarget의 값을 나눈값으로 줄여주고 소수를 저장합니다
        //iCurrentIndex의 값을 증가시켜 줍니다.
        //다시처음부터 제일큰 소수부터 검사를 시작합니다
        if (iTarget % Prime[i-1] == 0)
        {
            iTarget /= Prime[i-1];
            PrimeUsed[iCurrentIndex] = Prime[i-1];
            ++iCurrentIndex;
        }
        //소수의 나머지가 0이 아닐경우 다음 소수로 넘어갑니다
        else
        {
            --i;
        }
        //검사받는 숫자의 값이 1이 되면 검사를 종료합니다
        if (iTarget == 1)
            break;
    }
 
    //PrimeUsed 배열의 크기를 리턴합니다
    return iCurrentIndex;
}

프로그램을 제작하면면서 배운점

소수찾기 코드의 오버헤드를 줄였습니다.

for문에서 초기값의 자료형이 unsigned int 이고 증가식이 --으로 감소일때

0에서 --감소연산자가 발동하면 

i가 최대값으로 변하면서

무한루프에 빠지게 됩니다

unsigned int 사용시 주의 해야합니다