(구름 먼데이챌린지 c++ 1주차)4. 소수찾기

https://edu.goorm.io/learn/lecture/33428/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%A8%BC%EB%8D%B0%EC%9D%B4-%EC%B1%8C%EB%A6%B0%EC%A7%80-%ED%95%B4%EC%84%A4/lesson/1665444/1%EC%A3%BC%EC%B0%A8-%EB%B3%B5%EC%8A%B5%EB%AC%B8%EC%A0%9C-4-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0

goorm

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

using namespace std;

int main() {
	int n;
	int answer = 0;
	vector<int> num;
	vector<bool> prime(100001, false);
	
	cin >> n;
	
	for(int i = 2; i <= 100001; i++){
		for(int j = i + i; j <= 100001; j += i){
			prime[j] = true;
		}
	}
	
	num.push_back(0);
	
	for(int i = 0; i < n; i++){
		int A;
		
		cin >> A;
		
		num.push_back(A);
	}
	
	for(int i = 2; i <= n; i++){
		if(!prime[i]){
			answer += num[i];
		}
	}
	
	cout << answer;
	
	return 0;
}

주어진 n개의 수에서

i 가 소수일 때 위치한 숫자를 answer에 더해주면 된다.

 

우선 소수를 판별하기 위해 prime 벡터를 선언하여 false로 초기화 한다.

에라토스테네스의 체 기법을 이용해 false인 것들이 소수가 된다.

 

이를 이용하여 n개의 숫자 중 i번째 인덱스에 해당하는 수를 더해준다.

수는 1부터 시작해야 하기 때문에 n개의 수를 받는 벡터의 맨 처음은 0을 넣어주고 시작한다.

또한, 소수는 2부터 시작하기 때문에 마지막 for문도 2부터 시작하면 된다.