1978. 소수 찾기

1. Solution

• 내가 문제를 해결한 방법은, "2부터 n-1 수로 나누어 떨어진다면 소수가 아니다" 를 이용하여 해결하였다.
• 에라토스테네스 방법을 통하여 더 쉽게 해결 가능하다.

// 2 ~ n-1 의 수로 나눠떨어지는지 확인하는 방법으로 구현

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> nums;

int primeCount(vector<int> num){
    int count = 0; 

    for(int i = 0; i < num.size(); i++){
        // 소수는 1보다 큰 자연수 중, 1과 자신만을 약수로 가지는 수이다.
        if(num[i] == 1) continue;

        bool isPrime = true;

        for(int d = 2; d < num[i]; d++){
            if(num[i] % d == 0) isPrime = false;
        }
        if(isPrime) count += 1;
    }
    return count;
}

int main(){
    int n;

    // 사용자 입력받기
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> n;
        nums.push_back(n);
    }

    // 소수 개수 출력
    cout << primeCount(nums) << endl;
}

 

2. 알아야 할 개념

1) C++ 한줄 입력받기

• cin 은 띄어쓰기와 개행문자를 구분하지 못한다. (즉, cin 도 한 줄 입력이 가능하다.)
• getline() 이용한다. -> istream::getline(), string::getline() 

istream:: getline()	string::getline()
#include <cstring>	#include <string>
C언어 처럼 마지막에 널값 자동 추가
char ch[100]; cin.getline(ch, 10);	string str; getline(cin, str);

 

2) 소수 찾기 (소수: 1보다 큰 자연수 중에서 1과 자신만 약수로 갖는 수)

방법 1) 2 ~ n-1 수로 나눴을 때 0이 되면, 소수가 아니다.

방법 2) 에라토스테네스