에라토스테네스의 체, 이게 정말 빠른게 맞을까요? (깃 청부)
357
unchaptered
작성한 질문수 26
0
안녕하세요.
다른 분 풀이에서 "에라토스테네스의 체"라는 것이 있어서,
구글링 해보니 포스트에는 최적의 알고리즘 이라는 내용이 있었는데,
실제로 속도 비교를 해보니 오히려 성능이 좋지 않다 라고 느꼈습니다.
두 알고리즘에 사용된 소수의 특징 은 다음과 같았습니다.
1. 1은 소수가 아니다. (해당 값일 경우 바로 중단)
2. 2는 무조건 소수이다. (해당 값일 경우 바로 중단)
3. 4 이상의 수는 Math.sqrt 까지만 그 값을 반복한다.
문제 풀이에 2가지 쟁점을 잡아 풀었습니다.
3-1. 3번 알고리즘을 사용하기 위하여, 2와 4 사이의 유일한 정수인 3은 소수이므로 바로 중단한다
다른 분 풀이에서 "에라토스테네스의 체"라는 것이 있어서,
구글링 해보니 포스트에는 최적의 알고리즘 이라는 내용이 있었는데,
실제로 속도 비교를 해보니 오히려 성능이 좋지 않다 라고 느꼈습니다.
두 알고리즘에 사용된 소수의 특징 은 다음과 같았습니다.
1. 1은 소수가 아니다. (해당 값일 경우 바로 중단)
2. 2는 무조건 소수이다. (해당 값일 경우 바로 중단)
3. 4 이상의 수는 Math.sqrt 까지만 그 값을 반복한다.
문제 풀이에 2가지 쟁점을 잡아 풀었습니다.
3-1. 3번 알고리즘을 사용하기 위하여, 2와 4 사이의 유일한 정수인 3은 소수이므로 바로 중단한다
함수를 실행한 파일
성능 비교 (결과값은 모두 동일하게 출력)
기본 풀이 방법 코드
22-javascript-coding-test/2.Prime_numbers_basic.js at main · unchaptered/22-javascript-coding-test (github.com)
에라토스테네스의 체
22-javascript-coding-test/2.Prime_numbers_adv.js at main · unchaptered/22-javascript-coding-test (github.com)
에라토스테네스의 체에서 몇 가지 개선점이 상상되기는 하지만,
테스트할 수가 클수록 그 만큼 배열을 생성하는 데 걸리는 시간 이 길어지는 단점이 보이는데, 어째서 해당 알고리즘이 성능적으로 좋은지 모르겠습니다.
아니면 제가 Array.prototype.filter() 를 통해서 새로운 배열을 만들고 있기 떄문에 성능 저하 가 발생하고 있는 것일까요?
p.s. 강의 파일과 관련있는 코드라서 강사님 답변 받고 나면 바로 private 으로 돌려놓겠습니다.
p.p.s 이 부분은 궁금해서 커뮤니티 같은데에 질문을 남겨서 의견을 받아도 될까요? ㅠㅠ
에라토스테네스의 체
22-javascript-coding-test/2.Prime_numbers_adv.js at main · unchaptered/22-javascript-coding-test (github.com)
에라토스테네스의 체에서 몇 가지 개선점이 상상되기는 하지만,
테스트할 수가 클수록 그 만큼 배열을 생성하는 데 걸리는 시간 이 길어지는 단점이 보이는데, 어째서 해당 알고리즘이 성능적으로 좋은지 모르겠습니다.
아니면 제가 Array.prototype.filter() 를 통해서 새로운 배열을 만들고 있기 떄문에 성능 저하 가 발생하고 있는 것일까요?
p.s. 강의 파일과 관련있는 코드라서 강사님 답변 받고 나면 바로 private 으로 돌려놓겠습니다.
p.p.s 이 부분은 궁금해서 커뮤니티 같은데에 질문을 남겨서 의견을 받아도 될까요? ㅠㅠ
답변 0
continue를 사용하는 이유
0
102
2
정렬 가능 여부 판단하기
0
81
2
알고리즘 학습법 관련해서 질문드립니다.
0
96
1
코드 리뷰 부탁드립니다!
0
108
1
indexOf를 사용해서 풀어보았습니다 !!
0
76
1
저는 이런식으로 구현 해보았습니다 !!
0
70
1
12,13,14 강의 소리만 나오고 검은 화면입니다
0
113
3
반복문 최소화하고 indexOf 사용해서 풀어봤습니다
0
74
1
영상 보기 전에 직접 풀어봤습니다.
0
81
1
섹션1의 17번문제 이 풀이로 풀어도 될까요?
0
146
2
정규표현식으로 처리해도 상관없나요 ?
0
129
2
3칸씩 건너뛸 수 있을 경우
0
134
2
강의에 대해 질문있습니다.
0
145
2
Object와 Set을 이용해 풀어봤습니다.
0
133
2
이렇게 해도 되나요?
0
113
2
선생님 중복 단어나 중복관련 문제들은 set을 이용하면 좋을것 같습니다.
0
149
2
이렇게 풀어도 괜찮을까요?
0
146
1
이렇게 풀어도 괜찮을까요?
0
126
1
모든 아나그램 찾기에서 시간복잡도
0
106
1
코드리뷰 부탁드립니다.
0
142
1
for loop 탈출은 return 문으로 해도 되지 않나요?
0
137
1
투포인트알고리즘으로 풀어봤습니다.
0
148
0
코드 리뷰 부탁드립니다.
0
122
1
코드 맞게 작성한 거 아닌가여??
0
152
1