[프로그래머스] 소수 찾기 : C++

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

▶ 정답코드

#include <string>
#include <vector>
#include <math.h>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> v;
	for(int i = 1; i <= n; i++){
		v.push_back(i);
	}
	
	for(int i = 2; i <= n; i++){
		for(int j = 2*i; j <= n; j+= i)
			v[j] = 0;
	}
	
	for(int i = 2; i <= n; i++){
        if(v[i] != 0) answer++;
    }
    return answer;
}

기존에 sqrt()를 통해 범위를 정하고 나누어 떨어지면 소수가 아님을 판별하는 방식을 사용했으나, 효율성 테스트를 통과하지 못했다. 그러던 중 소수를 제외한 다른 수를 0으로 만드는 방법을 알게되었고 효율성 테스트를 통과할 수 있었다.

채점 결과

 

▶사용예시

#include <iostream>
#include <vector>
using namespace std;

int main(){
	int n = 100;
	vector<int> v;
	for(int i = 0; i <= n; i++){
		v.push_back(i);
	}
	
	for(int i = 2; i <= n; i++){
		if(v[i] == 0) continue;
		for(int j = 2*i; j <= n; j+= i)
			v[j] = 0;
	}
	
	for(int i = 0; i < v.size(); i++){
		cout << v[i] << ' ';
		if(i != 0 && i % 10 == 0) cout << '\n';
	}
}

실행 결과

 

▶실패한 코드

#include <string>
#include <math.h>

using namespace std;

bool judge(int n){
    if(n == 2) return true;
    int n_ = sqrt(n);
    for(int i = 2; i <= n_; i++){
        if(n % i == 0) return false; 
    }
    return true;
}

int solution(int n) {
    int answer = 0;
    for(int i = 2; i <= n; i++){
        if(judge(i)) answer++;
    }
    return answer;
}

 

 

 

 

 

참고자료 : https://touo.tistory.com/92