소수 구하는 알고리즘

 

 

n까지의 소수 출력하기

 

- 반복문

소수를 판단하기 위해서 2부터 모든 수를 나눠보지 않아도 된다고 한다

int n;
std::cin >> n;

for (int i = 2; i <= n; i++)
{
	bool isPrime = true;
    
	for (int j = 2; j * j <= i; j++)
    {
        if (i % j == 0)		// 1이 아닌 다른 수로
        {
        	isPrime = false;
            break;
        }
    }
    
    if (isPrime)
    {
    	std::cout << i << ' ';
    }
}

std::cout << '\n';

 

 

- 에라토스테네스의 체

 

반복문보다 이게 더 빠름

 

2부터 n까지의 모든 수를 나열

2는 소수이므로 저장하고 그 외 2의 배수들은 소수가 아니므로 지움

남은 수 중 3은 소수이므로 저장하고 그 외 3의 배수들은 소수가 아니므로 지움

남은 수 중 5는 소수이므로 저장하고 그 외 5의 배수들은 소수가 아니므로 지움

위와 같은 과정을 반복

#include <vector>

std::vector<bool> sieveOfEratosthenes(int n)
{
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
    
    return isPrime;
}

int main()
{
	std::vector<bool> primeList = sieveOfEratosthenes(120);
    
    for (int i = 2; i < primeList.size(); i++)
    {
        if (primeList[i])
        {
        	std::cout << i << ' ';
        }
    }
    std::cout << '\n';

	return 0;
}