26. 소수 찾기

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

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

제한 시간 안에 범위 안 소수를 모두 찾으려면 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하는 것이 좋습니다. 

파이썬

def solution(n):
    prime = [False, False] + [True] * (n-1)
    count = 0
    for i in range(2,n+1):        
        if prime[i]:
            count += 1
            for j in range(2*i, n+1, i):
                prime[j] = False
    return count
    
"""
효율성  테스트
테스트 1 〉	통과 (150.83ms, 24.8MB)
테스트 2 〉	통과 (148.43ms, 24.3MB)
테스트 3 〉	통과 (186.30ms, 24.8MB)
테스트 4 〉	통과 (151.41ms, 24.5MB)
"""

자바스크립트

function solution(n) {
    let prime = new Array(n+1).fill(true)
    prime[0] = false
    prime[1] = false
    let count = 0
    for (let i=2; i<=n; i++){
        if (prime[i] == true){
            count++
            for (let j=2;j*i<=n;j++) {
                prime[j*i] = false
            }
        }
    }
    return count
}

/*
효율성  테스트
테스트 1 〉	통과 (34.36ms, 44.6MB)
테스트 2 〉	통과 (35.30ms, 44.2MB)
테스트 3 〉	통과 (36.56ms, 44.4MB)
테스트 4 〉	통과 (35.51ms, 44.4MB)
*/

자바

class Solution {
    public int solution(int n) {
        var prime = new boolean[n+1];
        var answer = 0;
        for (var i = 2; i <= n; i++) prime[i] = true;
        for (var i = 2; i <= n; i++) {
            if (prime[i] == true) {
                answer++;
                for (var j = i * 2; j <= n; j += i) 
                    prime[j] = false;
            }
        }
        return answer;
    }
}

/*
효율성  테스트
테스트 1 〉	통과 (13.04ms, 52.3MB)
테스트 2 〉	통과 (14.52ms, 54.4MB)
테스트 3 〉	통과 (12.98ms, 52.6MB)
테스트 4 〉	통과 (13.36ms, 54.1MB)
*/

C#

public class Solution
{
    public int solution(int n)
    {
        int answer = 0;
        bool[] sieve = new bool[n + 1];

        for (int i = 2; i < n + 1; i++)
            sieve[i] = true;

        for (int i = 2; i <= n; i++)
        {
            if (sieve[i] == true)
            {
                answer++;
                for (int j = i * 2; j <= n; j += i) 
                    sieve[j] = false;
            }
        }
        return answer;
    }
}

/*
효율성  테스트
테스트 1 〉	통과 (20.34ms, 54.9MB)
테스트 2 〉	통과 (19.54ms, 56.6MB)
테스트 3 〉	통과 (19.35ms, 56.6MB)
테스트 4 〉	통과 (19.53ms, 54.9MB)
*/

 

golang

func solution(n int) (count int) {
	var arr = make([]bool, n+1)
	for i := 2; i <= n; i++ {
		arr[i] = true
	}
	for i := 2; i <= n; i++ {
		if arr[i] == true {
			count++
			for j := i * 2; j <= n; j += i {
				arr[j] = false
			}
		}
	}
	// fmt.Println(arr)
	return
}