1989번: 소수찾기

문제

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

---

풀이

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다.

 

• 1은 소수가 아니다.
• 2와 3은 소수이다.

위의 두 경우를 정해놓고 시작하면 4부터 소수인지 아닌지 체크하면 된다.

 

방법

n이 소수인지 구해야할 때,

2부터 시작해서 n까지 나눴을 때 한개라도 나머지가 0이면 소수가 아니다.

여기서 굳이 n까지 할 필요가 없이 n의 제곱근까지만 나눠보면 된다.

제곱근까지만 가운데에 있는 수이기 때문이다. 이 말이 무슨말이냐면

15 => 1x15, 3x5, 5x3, 15x1이다. 15의 제곱근은 3으로 15를 3까지만 나눠보면 모든 경우를 다 구해보는 것이다.

1x15나 15x1은 똑같기 때문 굳이 두번 계산할 필요가 없다.

14 => 1x14, 2x7, 7x2, 14x1. 14의 제곱근은 3이다.

 

 

4를 예를 들어보자.

• 4의 약수는 1, 2, 4이고, 1x4, 2x2, 4x1을 하면 4를 만들 수있다.
• 1x4와 4x1을 중복해서 계산할 필요는 없다.
• 4의 제곱근은 2이다.
• 4를 2로 나누면 나머지가 0이므로 소수가 아니다.

15를 예로 들어보자.

• 15의 제곱근은 3이다.
• 15를 2로 나누면 나머지는 0이 아니다.
• 15를 3으로 나누면 나머지는 0이다. => 소수 x

 

19를 예로 들어보자.

• 19의 제곱근은 4이다.
• 19를 2로 나누면 나머지는 0이 아니다.
• 19를 3으로 나누면 나머지는 0이 아니다.
• 19를 4로 나누면 나머지는 0이 아니다.
• 19는 소수이다.

 

---

소스 코드

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

int	check_prime(int n)
{
	int	i;

	if (n == 1)
		return (0);
	if (n == 2 || n == 3)
		return (1);
	i = 2;
	while (i <= sqrt(n))
	{
		if (n % i == 0)
			return (0);
		i++;
	}
	return (1);
}

int	main(void)
{
	int	N;	// N <= 100
	int	*ns;	// number <=1000
	int	index;
	int	count;

	count = 0 ;
	scanf("%d", &N);
	if (!(ns = (int *)malloc(sizeof(int) * N)))
		return (0);
	index = 0;
	while (index < N)
		scanf("%d", &ns[index++]);
	index = 0;
	while (index < N)
		count += check_prime(ns[index++]);
	printf("%d\n", count);
	return (0);
}