(12) [C++, Java] 백준 No.1929 : 소수 구하기

문제

풀이

자세한 풀이 : 

 

# C++(나의 풀이)

- endl을 썼다가 시간초과가 났으므로 "\n"을 사용하자.

- i*i 대신 i*2로 해준 방식으로 중복적인 연산이 존재하기 때문에 아래의 방식보다 불리하기 때문에 4ms정도 더 소요되지만
   크게 문제될 정도의 시간이 아니기 때문에 소수를 수집하여 컨트롤하기 좋은 이 방식을 선호하여 사용하는 것이 좋다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int m, n;               // 1 <= m <= n <= 1,000,000
    cin >> m >> n;

    vector<int> check(n+1); // 초기값은 defualt로 false임
    vector<int> prime_vec;

    check[0] = true;
    check[1] = true;

    for (int i = 2; i <= n; i++)
    {
        if (check[i] == false)
        {
            if (i >= m)
                prime_vec.push_back(i);

            for (int j = i*2; j <= n; j += i)
                check[j] = true;
        }
    }

    for (int i = 0; i < prime_vec.size(); i++)
    {
        cout << prime_vec[i] << "\n";
    }
}

 

# C++(백준 풀이)
- endl을 썼다가 시간초과가 났으므로 "\n"을 사용하자.
- "i*i <= n" 으로 오버플로우를 방지한 방법으로 중복연산이 없어서 효율이 더 좋다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int m, n;               // 1 <= m <= n <= 1,000,000
    cin >> m >> n;

    vector<int> check(n+1); // 초기값은 defualt로 false

    check[0] = true;
    check[1] = true;

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

    for (int i = m; i <= n; i++)
    {
        if (check[i] == false)
            cout << i << "\n";
    }
}

# Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean[] check = new boolean[m+1];
        check[0] = check[1] = true;
        for (int i=2; i*i <= m; i++) {
            if (check[i] == true) {
                continue;
            }
            for (int j=i+i; j<=m; j+=i) {
                check[j] = true;
            }
        }
        for (int i=n; i<=m; i++) {
            if (check[i] == false) {
                System.out.println(i);
            }
        }
    }
}