[Algorithm] 에라토스테네스의 체

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum

[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의

 

인프런 강의 22강에 대한 리뷰이다.

 

 

에라토스테네스의 체는 프로그래머스 소수찾기에서 다뤘던 터라 익숙한 개념이다.

 

https://binaryjourney.tistory.com/120

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

 

 

 

 

출처: 위키피디아

 

 

 

1) 시간 복잡도가 O(N)인 소수찾기

 

// C++
#include <stdio.h>


bool isPrimeNumber(int x) {
	for (int i = 2; i < x; i++) {
		if (x % i == 0 ) return false;
	}
	return true;
}

int main(void) {
	printf("%d", isPrimeNumber(100));
	return 0;
}

 

// Javascript

function isPrimeNumber(x) {
    for (let i = 2; i < x; i++) {
        if (x % i === 0) return false;
    }
    return true;
}

function main () {
    console.log(isPrimeNumber(100));
}

main();

 

# Python

def isPrimeNumber(x):
    for i in range(2, x + 1):
        if x % i == 0: return False
    return True
    
if __name__ == "__main__":
    print(isPrimeNumber(100))

 

 

// Java

public class Main
{
    private static boolean isPrimeNumber(int x) {
        for (int i = 2; i < x; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }
	public static void main(String[] args) {
		System.out.println(isPrimeNumber(100));
	}
}

 

Java로 하니까 엄청 오래 걸림...!

 

 

 

2) N**1/2 까지 소수를 찾으면 시간 복잡도를 줄일 수 있음(약수의 대칭 특징을 이용)

 

 

 

// C++
#include <stdio.h>
#include <math.h>

bool isPrimeNumber(int x) {
	int end = (int) sqrt(x);
	for (int i = 2; i <= end; i++) {
		if (x % i == 0 ) return false;
	}
	return true;
}

int main(void) {
	printf("%d", isPrimeNumber(97));
	return 0;
}

 

// Javascript

function isPrimeNumber(x) {
    const end = parseInt(Math.sqrt(x));
    for (let i = 2; i <= end; i++) {
        if (x % i === 0) return false;
    }
    return true;
}

function main() {
    console.log(isPrimeNumber(97));
}

main();

 

 

# Python

def isPrimeNumber(x):
    end = int(x ** (1/2))
    for i in range(2, end + 1):
        if x % i == 0: return False
    return True

if __name__ == "__main__":
    print(isPrimeNumber(97))

 

 

// Java

public class Main
{
    private static boolean isPrimeNumber(int x) {
        int end = (int) Math.sqrt(x);
        for (int i = 2; i <= end; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }
	public static void main(String[] args) {
		System.out.println(isPrimeNumber(97));
	}
}

 

 

3) 엄청나게 많은 수에서 소수 찾기 -> 배열 이용 (에라토스테네스의 체)

 

자세한 설명은 위에 참조한 링크에 있다.

 

(배수들을 제거함)

 

// C++
#include <stdio.h>

int number = 100000;
int a[100001];

void primeNumberSieve() {
	for (int i = 2; i <= number; i++) {
		a[i] = i;
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] == 0) continue;
		for (int j = i + i; j <= number; j+= i) {
			a[j] = 0;
		}
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] != 0) printf("%d", a[i]);
	}
}

int main(void) {
	primeNumberSieve();
	return 0;
}

 

// Javascript

let number = 100000;
let a = new Array(100001).fill(0);

function primeNumberSieve() {
    for (let i = 2; i <= number; i++) {
        a[i] = i;
    }
    for (let i = 2; i<= number; i++) {
        if (a[i] == 0) continue;
        for (let j = i + i; j <= number; j += i) {
            a[j] = 0;
        }
    }
    for (let i = 2; i <= number; i++) {
        if (a[i] !== 0) console.log(a[i]);
    }
}

primeNumberSieve();

 

 

# Python

number = 100000
a = [0] * 100001

def primeNumberSieve():
    for i in range(2, number + 1):
        a[i] = i
    for i in range(2, number + 1):
        if a[i] == 0: continue
        for j in range(i + i, number + 1, i):
            a[j] = 0
    for i in range(2, number + 1):
        if not a[i] == 0: print(a[i])

if __name__ == "__main__":
    print(primeNumberSieve())

 

// Java

public class Main
{
    private static int number = 100000;
    private static int[] a = new int[100001];
    private static void primeNumberSieve() {
        for (int i = 2; i <= number; i++) {
    		a[i] = i;
    	}
    	for (int i = 2; i <= number; i++) {
    		if (a[i] == 0) continue;
    		for (int j = i + i; j <= number; j+= i) {
    			a[j] = 0;
    		}
    	}
    	for (int i = 2; i <= number; i++) {
    		if (a[i] != 0) System.out.printf("%d ", a[i]);
    	}
    }
	public static void main(String[] args) {
		primeNumberSieve();
	}
}