소수 찾기 알고리즘

한가지 숫자가 소수인지 판별하는 알고리즘

bool isPrime(int num) 
{ 
	if (num == 1) // 1은 소수가 아니므로 제외
		return false; 
	else if (num >= 2 && num <= 3) // 2와 3은 간단하므로 바로 return
		return true; 
	else 
	{ 
		for (int i = 2; i < num / 2; i++) // num/2까지 검색을 하면 속도가 빨라짐
		{ 
		if (num % i == 0) 
			return false; 
		} 
	} 
	return true; 
}

 

num/2까지 반복문을 돌리면 num을 모두 확인하는것보다 시간이 빠르다.

시간을 더 단축하기 위해서는 sqrt(num)까지 검색하는 방법도 존재한다.

---

Sieve of Ertosthenes(에라토스테네스의 체)를 이용한 넓은 범위의 소수를 찾는 알고리즘

void ErtosthenesPrimeNumbers(int num)
{
    // 입력받은 갯수만큼 배열을 만들고 모두 true로 초기화
	bool *arr;
	arr = (bool*)malloc(sizeof(bool) * num);
	memset(arr, true, sizeof(arr));
	
    // 2부터 검색을 시작하며 2가 true이면 2,4,6,8...모두 false로 변환 3이 true이면 3,6,9..를 false로
	for (int i = 2; i*i <= num; i++)
	{
		if (arr[i] == true)
		{
			for (int j = i * i; j <= num; j += i)
				arr[j] = false;
		}
	}
	
    // true인 숫자들만 출력
	for (int i = 2; i <= num; i++)
	{
		if (arr[i])
			std::cout << i << " ";
	}
	std::cout << std::endl;
}

1000, 10000등 큰수내에 존재하는 소수를 알아낼때 쓰일 수 있는 알고리즘이다. 유클드 호제법, 페르마의 소정리, 윌슨의 정리등이 존재한다.