[C]1부터n까지 소수구하기

 

 

 

 

1. 배열 ?

 

 

소수구하기 문제를 풀기 위해서는 '배열'에 대한 개념을 알아야 한다.

--> 반복문을 통해 배열에 값을 넣어주어야 하기 때문!

 

 

> 배열 방 예시

위와 같은 배열의 방(index)가 있다고 가정,

 

> 각 배열 방에 값이 있는 예시

각 방에 값을 저장하는 것이 배열의 쓰임새다.

 

 

 

 

 

2. 포인터 ?

 

 

포인터는 어떤 것을 가리킨다.

 

> 포인터 선언 예시

포인터는 '변수'의 '주소값'을 가리킨다.

 

예를들어, 변수에 포인터를 붙인다면 그 변수의 주소값을 저장하고 있다는 뜻이다.

--> 사용 : 주소값을 저장시킨 포인터를 사용한 함수의 리턴값으로, 저장되어 있는 소수의 집합을 가져올 수 있다!

 

 

 

 

3. 사용할 알고리즘

 

 

< 제곱근을 이용한 소수 구하기 >

 

- 사용 이유 

1) 소수가 될 숫자 n은 1과 자신 외에 나눠지는 수가 없어야 한다.

2) 1부터 n까지의 수 중 소수는 2,3,5,...,어떤 것 이다.

3) n의 제곱근은 n을 나눌 수 있는 수이다.

4) n의 제곱근으로 나눌 수 있다면 n은 소수가 아니다.

 

 

> 수직선 상 예시

- 근거

#1 1<Y<139 반복문

#2 139 = X * Y (이때, 1<X<=Y)

#3 X와 Y의 범위에서 X*Y시 139가 나오지 않음을 전제

 

--> Y가 1부터 139까지 반복하는 중에, X의 값도 반복이 된다.

--> X와 Y가 동일한 수가 되어 #2의 상황이 이루어 진다면 n(139)는 소수가 아님

--> X와 Y가 동일하게 되는 수는 139의 제곱근이다.

--> X와 Y가 제곱근일 경우에는 곱해서 139가 될 수 있으며 소수가 아니다.

--> 따라서 1부터 139의 제곱근의 경우에서 소수를 판별할 수 있다.

 

 

 

4. 코드

 

 

#include <stdio.h>
#include <math.h>

int* getPrime(int input) {
	int i, j;
	int result;
	int count = 1;
	int* getNum;
    
	getNum = (int*)malloc(sizeof(int) * input);

	for (i = 2; i <= input; i++) {
		if (i == 2) {
			getNum[count] = i;
			count++;
		}
		if (i == 3) {
			getNum[count] = i;
			count++;
		}

		for (j = 2; j <= (int)sqrt(i); j++) {
			if (i % j == 0) {
				/* 소수 아님 */
				break;
			}
			else { 
				if (j == (int)sqrt(i)) {
					// sqrt(i) 까지 나눴는데도 안나눠짐, 즉 소수
					getNum[count] = i; 
                    count++;
				}

			}


		}
	}

	getNum[0] = count;
	
	return getNum;
}

void main() {

	int n, i;
	int first;
	int* result;

	printf("소수를 구할 범위를 입력해주세요.\n");
	scanf_s("%d", &n);

	result = (int)malloc(sizeof(int) * n);

		result = getPrime(n);
	

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

 

 

> 코드 실행화면

 

 

1. i가 2인 경우와 3인 경우를 따로 분리한 이유

- 2와 3인 경우 제곱근의 값이 반복문 초기화한 값보다 작아지기 때문에 반복문 성립이 안된다.

 

2. if(j == (int)sqrt(i))를 조건으로 둔 이유

- 초기 코드는 j가 i를 한 번이라도 나누지 못하면 소수로 판별함. ex) i = 105, j = 2

- 처음 숫자(ex 2)로 나누지 못했을 때 j 반복문으로 돌아가 다시 수행하기 위한 작업이 필요

 

- ex) i = 11, j = 2

#1 if > 11 % 2 != 0

#2 else > 2 != √11(3) --> 다시 j 반복문으로 올라감, j 증가

#3 #1, #2의 경우 반복

#4 else > 3 == √11(3) 본인은 나눌 수 없다 (=본인은 소수가 아니다) 따라서 조건 만족, 소수

 

 

 

 

5. 오류 사항

 

 

1) i가 2와 3일 경우에 출력이 안되는 문제 

- √2와 √3의 값이 j의 초기값 보다 큼 --> i 반복문에서 예외상황 해결

 

2) 나오지 않아야 할 수 (9, 105, ...)가 나옴

- if(나눠질 경우 소수가 아님), else(나눠지지 않은 경우) 단순히 두 작업으로 인해 

- j의 초기값 혹은 그 다음 값에서 한 번 나눠지지 않았다고 소수라고 인식함

- j == (int)sqrt(i) 의 경우 추가로 j의 값을 늘려주는 for문의 처음으로 돌아가기

 

 

 

 

6. 정리

 

학부시절 과제로 냈었던 기억이 있다.

그 당시에는 2부터 입력받은 n-1까지 다 나눠서 나눠지는 수가 없다면 소수로 판별했던 것이 기억난다.

문제의 의도를 제대로 파악하지 않고 프로그래밍을 했었는데, 그것 때문에 좀 많이 돌아갔다.

소수와 약수를 헷갈려 코딩해서 원하는 결과가 나오지도 않았고 쓰레기 값도 종종 나왔다.

또한, 포인터를 사용하는데에 있어서 헷갈리는 점이 있었다.

포인터를 반환해서 main함수에서 호출하는 것, 배열을 불러오는 것등에 어려움이 있었다.

이 문제를 푸는 관건은 1) 1부터 제곱근까지 나눈다는 점 활용, 2) 포인터와 배열을 사용한다는 점

두가지에 초점을 맞췄다.