프로그래머스 - level 1 소수 찾기

pa324·2019년 11월 29일
0

문제

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

풀이

  • 에로타스테네스의 체를 이용해서 소수를 찾으면 된다.
    • 120까지의 모든 소수를 구한다고 해보자. 2부터 120까지 배열에 모두 넣은 후 소수가 아닌 것들을 모두 체크해버리는 것이다.
    • 2를 제외한 모든 2의 배수를 체크한다.
      • 3을 제외한 모든 3의 배수를 체크한다.
      • 4는 2의 배수에서 체크 되므로 소수 아님.
    • 체크가 안된 수들이 소수이다.

코드

시간초과 코드

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

int solution(int n) {
    int answer = 0;
    
    for(int i = 2; i <= n; i++) {
        
        int count = 0;
        
        for(int j = 2; j*j <= i; j++) {
            if(i % j == 0) {
                count++;
            }
        }
        if(count == 0) answer++;
    }
    return answer;
}

에라토스테네스의 체

#include <string>
#include <vector>
using namespace std;
int numbers[1000000] ;
int solution(int n) {

    int answer = 0;
 
    
    for(int i = 2; i <= n; i++) {
        if(numbers[i] == 1) continue;
        for(int j = i*2; j <= n; j+=i) {
            
            numbers[j] = 1;
            
        }
    }
    
    for(int i = 2; i <= n; i++) {
        if(numbers[i] == 0) answer++;
    }
    
    return answer;
}
profile
안녕하세요

0개의 댓글