[c++,Swift] 프로그래머스 소수 찾기

프로그래머스:  소수 찾기 ->  링크

코딩테스트 연습 - 소수 찾기 | 프로그래머스

 

이론 참고 :

2020/01/15 - [알고리즘_자료구조/이론정리] - 소수 구하기 - 에라토스테네스의 체

 

풀이 

c++

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int *arr;
    arr = new int[n+1];
    int i = 2;
    int result = 0;
    
    for (i = 2; i <= n; i++)
    {
        arr[i] = i;
    }

    for (i = 2; i <= n; i++)
    {
        if (arr[i] == 0)
            continue;
        for (int j = i + i; j <= n; j += i)
        { 
            arr[j] = 0;
        }
    }
    
    for (i = 2; i <= n; i++)
    {
        if (arr[i] != 0)
            result++;
    }
    
    return result;
}

Swift

func solution(_ n:Int) -> Int {
    var arr = [Int].init(repeating: 0, count: n+1)
    var result = 0
    
    for index in 2...n {
        arr[index] = index
    }
    
    for index in 2...n {
        if arr[index] == 0 {
            continue
        }
        
        var j = index + index
        while(j <= n) {
            arr[j] = 0
            j += index
        }
    }
    
    for index in 2...n {
        if arr[index] != 0 {
            result += 1
        }
    }
    
    return result
}