[백준] 4948 베르트랑 공준 (C++)

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

4948번: 베르트랑 공준

 

 

 

 

 

 

 

 

 

 

 

---

 

풀이

 

 

#include<iostream>
#include<cmath>
#include <vector>

using namespace std;

int nums[250000];

bool find(int num)
{
    for (int j = 2; j <= sqrt(num); j++)
    {
        if (nums[num] == 0)
            return true;
        else if ((num) % j == 0)    //소수가 아님
        {
            nums[num] = 0;
		return true;
        }
    }
    return false;   //소수임
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);


    for (int i = 0; i < 250001; i++)
        nums[i] = i;


    int n;
	vector<int> ns;

    while(true)
    {
        cin >> n;

        if (n == 0)
            break;

   		ns.push_back(n);
    }


    for (int j = 0; j < ns.size(); j++)
    {
        int result = 0;
        for (int i = ns[j] + 1; i <= 2 * ns[j]; i++)
        {
            if (i == 2)
                result++;
            else if (!find(i))
                if (i <= 2 * ns[j])
                    result++;
        }

        cout << result << "\n";
    }

   
    return 0;
}

 

 

'에라토스테네스의 체' 를 활용하여 풀어야 시간초과가 나지 않는다

 

에라토스테네스의 체는 시간복잡도 O(n ^1/2) 를 가지며  n 까지의 소수를 구하고자 할 때 2부터 n의 제곱근까지 돌아가며 모든 배수들은 제외시켜 소수만 남기는 알고리즘이다

 

해당 코드는 배수를 제외시키지는 않았다n까지의 수를 모두 배열로 만든 뒤, 소수가 아님이 판별난 숫자는 0으로 치환했다그리고 0으로 치환된 숫자는 더이상 소수인지 아닌지 계산할 필요가 없으므로 시간이 절약된다