[소수] 1978. 소수 찾기

1. 문제 해결 전략

시간복잡도의 제한이 없다면 정말 쉬운 문제이다. 소수란 자신(특정 수)보다 작은 수들로 나눴을 때

나머지가 0인 경우가 없는 수를 의미한다. (1은 제외이기 때문에 제외)

시간복잡도는 O(n)이 걸리기 때문에 만약 그 이하의 시간을 요한다면 에라토스테네스의 체 방식을 사용해야한다.

 

먼저, 일반적인 코드를 보자.

 

#include <iostream>

using namespace std;
int nums[1001] = { 0, };
bool IsPrime(int num)
{
	// 자기보다 작은수들로 나눈 나머지가 0이아니라면 소수
	if (num == 1) return false;
	for (int i = 2; i < num; i++)
	{
		if (num %i == 0)return false;
	}
	return true;
}
void printPrimeNumber(int N)
{
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		if (IsPrime(nums[i]))
		{
			count++;
		}
	}

	cout << count;
	cout << endl;
}

int main()
{
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> nums[i];

	printPrimeNumber(N);
	return 0;
}

최악의 경우 N번의 반복이 일어나는 코드이다.

 

에라토스테네의 체는 소수가 아닌 수들은 그 약수들이 대칭을 이룬다는 점을 이용해서 수의 제곱근까지만 계산하는 방식이다. 따라서 시간 복잡도는 O(N^(1/2))가 된다.

#include <iostream>
#include <math.h>

using namespace std;

int Max = 100000;
int bowl[100001];
void PrimeNumberSieve()
{
    //모든 값들을 1~max까지의 값으로 초기화
	for (int i = 1; i <= Max; i++)
	{
		bowl[i] = i;
	}
	// 소수판별은 2부터
	for (int i = 2; i <= Max; i++)
	{
        //이미 자기 자신이 셈이 됐다면 다음 수로 넘어간다
		if (bowl[i] == 0) continue;
		// 자신은 건너뛰고 그 다음 배수 부터 계산. 소수가 아닌 값은 0이된다
		for (int j = i + i; j <= Max; j += (i))
		{
			bowl[j] = 0;
		}
	}

	for (int i = 1; i <= Max; i++)
	{
		if (bowl[i] != 0)
			printf("%d ", bowl[i]);
	}
}

int main(void)
{
	PrimeNumberSieve();
	return 0;
}

 

 

2. 걸린 시간

10초?

 

3. 느낀점

 

 

4. 링크

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