Algorithm/알고리즘 스터디(2021.07)
[Algorithm] 에라토스테네스의 체
binaryJournalist
2021. 10. 4. 23:10
반응형
[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의
알고리즘을 배우며, 실무에서는 알고리즘이 어떻게 활용되는지 알아봅니다., [임베딩 영상] 알고리즘의 개요와 실습 환경 구축 알고리즘은 문제를 해결하는 절차입니다.입력, 출력, 유한성, 명
www.inflearn.com
인프런 강의 22강에 대한 리뷰이다.
에라토스테네스의 체는 프로그래머스 소수찾기에서 다뤘던 터라 익숙한 개념이다.
https://binaryjourney.tistory.com/120
[프로그래머스] 소수 찾기
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 효율성 체크도 있기 때문에 잘 생각해야 한다. ** Javascript 1) 첫 제출 (정확성 테스트는 통과하나 효율성 테스트에서 실..
binaryjourney.tistory.com
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();
}
}반응형