양의 정수 값을 입력 받아 입력한 정수까지의 소수를 구하는 함수 작성 - 공부하는 도비

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

예를 들어, 7은 1×7 또는 7×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 7은 소수이다. 

 

따라서, 1과 자기자신을 제외한 수로 나눠진다면 그 수는 소수가 아니다. 

이 점을 이용하여 소수를 계산해보려고 한다.

#include <stdio.h>

void prime(int a) {
    
    for(int i = 1; i <= a; i++)
    {
        int count = 0;
        
        for(int j = 1 ; j <= i; j++)
        {
            if (i % j != 0)
            {
                count += 1;
            }
        }
        if (count == i-2)
        {
            printf("%d ", i);
        }
    }
}

int main() {
	int num;
	scanf("%d", &num);
	prime(num);
	
	return 0;
}

입력된 수가 10이면  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 중 소수를 골라내야 한다. 

소수를 판정하기 위해서 코드에선 count라는 변수를 사용하였다. 

 

1부터 10까지 for문을 돌다가,  5라는 수가 소수 인지 아닌지는, 저 초록색 부분으로 나눠지지 않고, 빨간색 부분으로만 나눠진다면 이 수는 소수이다. 

따라서 초록색 부분으로 나눴을 때, 나눠지지 않으면 카운트를 올리고 

최종적으로 1과 자기 자신을 제외하여 count값이 자기 자신보다 2 작으면 소수로 판정한다. 

 

결과