[C++]프로젝트 오일러 10번 문제&풀이 (이백만 이하 소수의 합)

문제

10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다.

이백만(2,000,000) 이하 소수의 합은 얼마입니까?

 

접근방법(1차) - 코드는 맨 밑에!

1. 2부터 2,000,000까지 차례로

2. 1부터 해당 숫자까지로 나눠봐서, 나누어 지는 값이 2개이면 소수이므로 벡터에 저장하고,

3. 2보다 크면 그 숫자는 나누기를 중단한다.

4. 이렇게 저장된 벡터 요소의 합을 계산하면 끝

→ 시간이 너무 오래 걸린다ㅠㅠ

개선사항

1. 2부터 2,000,000까지 모든 숫자를 나눠봐야 하므로 연산량이 많다.

2. 단순한 방법으로 하려 했지만 계산에 너무 많은 시간이 걸리므로, 에라토스테네스의 체를 사용하기로 결정!

접근방법(2차)

1. 에라토스테네스의 체를 사용!

2. 벡터에 숫자를 일단 2,000,000까지 다 넣고 시작.

3. 2부터 시작해서 2의 배수는 벡터 값을 0으로 만든다.

4. 3 이후로도 같은 방법으로 실시하되, 벡터 값이 0이면 아예 계산에서 배제한다.

→ 앞에서 0으로 만든 값은 소수 판별여부 확인 작업에서 열외되기 때문에, 연산량을 획기적으로 줄일 수 있다.

 

접근방법(2차) 코드

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main()
{
    long long num = 2000000;
    long long sum = 0;

    vector<long long> era;

    for (long long i = 1; i <= num; i++)
    {
        era.push_back(i);
    }

    era[0] = 0; // era[0] = 1 -> 0

    for (long long j = 1; j < num; j++)
    {
        if (era[j] != 0)
        {
            for (long long k = (j + 1) * 2; k <= num; k += (j + 1))
            {
                era[k - 1] = 0;
            }
            sum += era[j];
            //cout << j + 1 << " :\t" << era[j] << endl;
        }
    }

    cout << "Answer is : " << sum << endl;
    
    return 0;
}

 

접근방법(1차) 코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int count = 0;
    long long con = 0;
    vector<long long> num_vec;

    for (long long num = 2; num <= 2000000; num++)
    {
        for (long long i = 1; i <= num; i++)
        {
            if (num % i == 0)
            {
                count += 1;
            }
            if (count > 2)
                break;
        }
        if (count == 2)
        {
            num_vec.push_back(num);
            //cout << num << endl;
        }
        count = 0;
    }

    int end_num = num_vec.size();

    for (int i = 0; i < end_num; i++)
    {
        con += num_vec[i];
    }
    cout << "Answer is : " << con << endl;
    return 0;
}

 

참고

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler