[자료구조] : 소수의 나열 (C)

이번 시간에는 소수의 나열에 대해 알아보겠다.

소수란? 자신과 1이외의 정수로 나누어 떨어지지 않는 정수다.

대표적으로 13은 어떤 정수로도 나누어 떨어지지 않는다.

아이디어

• 식으로 표현하면, 2부터 n-1까지의 어떤 정수로도 나누어 떨어지지 않는다.

• 만약에 나누어 떨어지는 정수가 하나 이상 존재하면 그것은 합성수다.

  1000 이하의 소수를 나열하는 다음 예제를 보자.

#include <stdio.h>


int main()
{
	int i, j;
	unsigned long counter = 0; // 나눗셈의 횟수를 계산할 변수
	for (i = 2; i <= 1000; i++) //1를 제외한 나머지 수 i = 2
	{
		for (j = 2; j < i; j++)
		{
			counter++;
			if (i % j == 0)
			{
				break;
			} //i를 나눈 나머지가 0으로 떨어지면, 즉 약수면 break로 빠져나오고
		}
		if (i == j)
			printf("%d\n", i);
	}
	printf("나눗셈을 실행할 횟수 ㅣ %lu\n", counter);


}

<결과>

• 9일 떄 소수인지 판단하는 방법(for)문 내부

  1. for문에서 j값이 2,3,,,,8로 증가한다. 9는 j가 3일 때, 나누어떨어지므로 break문이 동작하여 for문의 반복이 중단된다.
  2. 나눗셈은(counter)는 2,3 총 2회만 진행한다.

• 13일 때 소수인지 판단하는 방법(for)문 내부

  1. j값이 2,3,,,,12로 증가한다. 13은 단 한 번도 나누어 떨어지지 않는다. for문을 벗어날 때 j의 값은 13이다.

• 안쪽 for문의 반복이 종료된 시점에서 변수 j의 값은 아래와 같다.

  • 변수 i가 소수인 경우 : i과 같은 값 (for문이 끝까지 실행된다)
  • 변수 i가 합성수인 경우 : i보다 작은 값(for문이 중단된다.)

위와 같은 예제를 다른 알고리즘으로 풀어봤다.

#include <stdio.h>


int main()
{
	int i, n;
	int prime[500];
	int ptr = 0;
	unsigned long counter = 0;
	prime[ptr++] = 2; // prime[0] = 2
	for (n = 3; n <= 1000; n += 2)
	{
		for (i = 1; i < ptr; i++) // ptr의 값은 1이다. for문의 제어식인 i < ptr(1<1)이 성립하지 않는다. => for문 실행하지 않음 
			//ptr == i (1 == 1)이 참이므로 prime[ptr++]에 n를 대입한다.
			counter++;
			if (n % prime[i] == 0)
				break;

		if (ptr == i)
			prime[ptr++] = n;
	}
	for (i = 0; i < ptr; i++)
	{
		printf("%d\n", prime[i]);

	}
	printf("나눗셈을 실행한 횟수 : %lu\n", counter);
	return 0;



}

• 소수를 구하는 과정에서 구한 소수를 prime의 배열의 요소로 저장한다.
• n이 소수인지를 판단할 때 쌓아 놓은 소수로 나눗셈을 한다.
• 2는 소수이므로 prime[0] = 2에 저장한다.
• ptr 변수는 배열에 저장한 소수의 개수를 나타낸다.
• 3이상의 소수는 이중 for문으로 구한다.
  • 바깥 for : n의 값을 2씩 증가시켜 3, 5, 7, 9 홀수 값으로 생성한다.
  • 안쪽 for : i값을 1부터 시작해서 ptr -1 만큼 진행한다.

• 5가 소수인지 판단하는 과정

  • prime[1]에 저장한 3으로 나눗셈을 실행한다. 3으로 나누어 떨어지지 않기 때문에 n의 값 5를 prime[2]에 저장한다.

• 7이 소수인지 판단하는 과정

  • prime[1]에 저장한 3과 prime[2]에 저장한 5로 나눗셈을 실행한다.
  • 소수라고 판단되면 n의 값 7을 prime[3]에 저장한다.

다음은 어떤 정수 n은 다음 조건을 만족하면 소수라고 판단할 수 있다.

  n의 제곱은 이하의 어떤 소수라도 나누어떨어지지 않는다.

곱셈과 나눗셈의 계산을 위한 프로그램을 작성해보자.

#include <stdio.h>


int main()
{
	int i, n;
	int prime[500];
	int ptr = 0;
	unsigned long counter = 0;
	prime[ptr++] = 2; // 2는 소수다.
	prime[ptr++] = 3; // 3은 소수다.
	for (n = 5; n <= 1000; n += 2) // 홀수만을 대상으로 한다. 
	{
		int flag = 0;
		for (i = 1; counter++, prime[i] * prime[i] <= n; i++)
		{
			counter++;
			if (n % prime[i] == 0) // 나누어 떨어지면 소수가 아니다.
				flag = 1;
				break;
		}
		if (!flag) //마지막까지 나누어 떨어지지 않는다.
		{
			prime[ptr++] = n; // 배열에 저장한다.
		}

	
	}
	for (i = 0; i < ptr; i++)
	{
		printf("%d\n", prime[i]);
	}
	printf("곱셈과 나눗셈을 실행한 횟수  : %lu\n", counter);


	return 0;


}

<결과>

핵심코드를 찾아보자.

<1>

for (n = 5; n <= 1000; n += 2) // 홀수만을 대상으로 한다. 
	{
		int flag = 0;
		for (i = 1; counter++, prime[i] * prime[i] <= n; i++)
		{
			counter++;
			if (n % prime[i] == 0) // 나누어 떨어지면 소수가 아니다.
				flag = 1;
				break;
		}
		if (!flag) //마지막까지 나누어 떨어지지 않는다.
		{
			prime[ptr++] = n; // 배열에 저장한다.
		}

	
	}

• 바깥 for문

  • 홀수만을 대상으로 하는 for문이 돌고있다.

• 안쪽 for문

  • 보통 쉼표 식 op1, op2를 평가할 때, 먼저 op1을 평가하고, 그 다음에 op2를 평가한다.
  • 이 식 전체를 평가하여 얻는 값은 오른쪽 연산자 op2를 평가하여 얻은 자료형을 가진 값이다.
  • counter++를 평가 -> counter를 증가시키고,
    오른쪽 피 연산자 prime[i] * prime[i] <= n을 평가.
  • for문을 반복 여부는 prime[i] * prime[i] <= n에 달려있다.

• 핵심 아이디어

 곱셈 : prime[i] * prime[i]
 나눗셈 :  n % prime[i]