소수 찾기 / 소수 구하기 _ 백준 1978,1929

1978번, 1929번 문제는 소수와 관련된 문제이다.

---

 

어떤 수 N이 소수가 아니라면, N = a * b 라고 표현할 수 있는데, 이떄 a와 b의 차이가 가장 적은 경우는 √n 이다.

그러므로, 검사를 n까지만 해서, 소수를 찾을 수 있다. 

 

이러한 소수의 특징을 이용하면,  아래와 같은 함수를 만들 수 있다. (true = 소수 false = 소수아님)

bool prime(int n)
{
	if (n < 2)
		return false;
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}

 

1978번의 경우, 주어진 수 N에서 소수의 개수를 찾는 프로그램이므로 위의 함수를 활용해 

#include <iostream>
#include <cstdio>
using namespace std;

bool prime(int n)
{
	if (n < 2)
		return false;
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}

int main(void)
{
	int count;
	int result = 0;
	int num[100];
	scanf("%d", &count);
	for (int i = 0; i < count; i++)
	{
		scanf("%d", &num[i]);
		if (prime(num[i]))
			result++;
	}
	printf("%d", result);
	return 0;
}

---

1929번은 일정 범위에서의 소수를 모두 출력하는 프로그램이므로, 

매번 prime함수로 해결하기는 어렵다.

 

그렇기 때문에, 여기서는 에라토스테네스의 체를 활용하는 방법을 사용할 것이다.

에라토스테네스의 체는 2부터 N까지의 수를 모두 적어두고, 아직 지워지지 않은 수 중 가장 작은수는 소수이며, 그 수의 배수를 모두 지우는 것을 반복한다.

즉, 2 - 3 - 5 - 7 - ...의 순서대로 배수가 지워지고, 남은 수는 소수가 되는 것이다.

→ 해당 부분을 for 구문 내에 구현한다.

 

따라서, 해당 문제에서는 먼저 제공된 범위에서 소수를  찾고, 입력받은 값 내에서 해당되는 소수를 출력하는 방식으로 코드를 구성하면 된다.

#include <iostream>
#include <cstdio>
using namespace std;

int main(void)
{
    int pn = 0;
    bool check[1000000];
    check[0] = check[1] = true;
    for (int i = 2; i * i < 1000000; i++)
    {
        if (check[i] == false)
        {
            for (int j = i + i; j <= 1000000; j += i)
                check[j] = true;
        }
    }
    int a, b;
    scanf("%d %d", &a, &b);
    for (int i = a; i <= b; i++)
    {
        if (check[i] == false)
            printf("%d\n", i);
    }
    return 0;
}