[C] 백준 | 1978번 코드 - 소수찾기

>문제

> 핵심

반복문 돌기.

효율적인 알고리즘을 강구해보자.

>풀이과정

[소수 : 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수. ]

 

소수 찾기

알고리즘 기본서에 꼭 나오는 내용으로 기억한다. 물론 나는 다 까먹었지만.

 

소수를 찾는데는 여러 전략이 있다.

제일 쉬운건 역시 2부터 n-1까지 일일히 나머지를 해보는것.

코드는 간단하지만 만약 수가 커진다면 시간적으로 그닥 효율적이지 못하다.

 

나도 기억이 가물가물해서 구글링으로 찾아봤다.

1. 절반까지만 반복문 돌기

소수는 1과 자기자신만으로 나누어 떨어지는 수이므로, 약수가 1과 자기자신 밖에 없다.

 

24는 약수로 1, 2, 3, 4, 6, 8, 12, 24 를 갖는다.

그리고 1과 24, 2와 12, 3과 8, 4와 6은 하나의 짝을 이루어 24를 만든다.

그러므로 절반 지점까지만 반복문으로 나누어 보았을때 약수가 나오지 않는다면, 그 수는 소수인 것이다.

2. 제곱근까지만 반복문 돌기

1번과 거의 똑같다.

제곱근을 기준으로 약수들이 한 쌍을 이루어 특정 정수를 이루는데 (2,24) (3,8) (4,6)

제곱근 이하 약수가 1밖에 없다면 그 수는 당연 소수인것이다.

3. 에라토스테네스의 체

1을 지운다 

2는 소수! | 2의 배수는 모두 거른다 (체로 거른다)

3은 소수! | 3의 배수는 모두 거른다 (체로 거른다)

4는 걸러졌다

5는 소수! | 5의 배수는 모두 거른다

6은 걸러졌다

7은 소수! | 7의 배수는 모두 거른다

..반복..

을 거치며 소수를 찾는 알고리즘이다. 

그냥 제곱근까지 반복문 돌면서 찾는게 낫겠다.

넓은 범위에서 소수를 찾는데 매우 유용하게 사용된다!!!

>>sedangdang.tistory.com/38

[C] 백준 | 1929번 코드 - *소수 구하기

>깨달은점

하나의 문제를 푸는데도 무궁무진한 방법이 있다.

이래서 요즘 초등학교부터 코딩교육을 시키는거구나 싶다. 창의력 대장으로 자라겠구만.. 

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int i, j, n, num, cnt;

	scanf("%d", &n);

	for (i = 0, cnt = 0; i < n; i++)
	{
		scanf(" %d", &num);

		for (j = 2; j < num; j++)
		{
			if (num % j == 0)
				break;
		}
		if (j == num)
			cnt += 1;
	}

	printf("%d\n", cnt);

	return 0;
}