(11) [C++, Java] 백준 No.1978 : 소수 찾기

문제

풀이

자세한 풀이 : 

 

# C++ => O(N루트N)
- N = 100, 'N루트N' = 1000으로 1억에 못미치는 값이므로 문제없다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool is_prime(int n)
{
    bool flag = true;

    if (n < 2)
        return false;

    for (int i = 2; i*i <= n; i++)
    {
        if (n % i == 0){
            return false;          // 여기서 return을 해주면 break문이 필요 없음
        }
    }

    return flag; 
}


int main(){
    int n;
    cin >> n;

    vector<int> vec(n);
    
    for (int i = 0; i < n; i++)
        cin >> vec[i];

    int count = 0;
    for (int i = 0; i < n; i++)
    {
        if(is_prime(vec[i]))
            count ++;
    }
    
    cout << count;
}

# C++ => O(N^2)

- N = 100, 'N^2' = 10000으로 1억에 못미치는 값이므로 문제없다.

bool is_prime(int n)
{
    ...
    for (int i = 2; i <= n/2; i++){
        ...
    }
   ...
}

# C++ => O(N^2)

- N = 100, 'N^2' = 10000으로 1억에 못미치는 값이므로 문제없다.

bool is_prime(int n)
{
    ...
    for (int i = 2; i <= n-1; i++){
        ...
    }
   ...
}

# Java

import java.util.*;
public class Main {
    public static boolean is_prime(int x) {
        if (x <= 1) {
            return false;
        } else if (x == 2) {
            return true;
        }
        for (int i=2; i*i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        while (n-- > 0) {
            if (is_prime(sc.nextInt())) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}