-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
15번 질문입니다.
21.07.22 20:37 작성 조회수 89
0
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
int main()
{
//freopen("input.txt", "rt", stdin);
int N;
scanf("%d", &N);
bool* isPrime = new bool[N+1];
for (int i = 0; i < N+1; ++i)
isPrime[i] = true;
for (int i = 2; i < N+1; ++i)
for (int j = 2 * i; j < N+1; j += i)
isPrime[j] = false;
int cnt = 0;
for (int i = 2; i < N+1; ++i)
if (isPrime[i])
cnt++;
printf("%d\n", cnt);
if (isPrime)
delete[] isPrime;
return 0;
}
강의시간에 보여주신 코드와 비교했을 때, Big(O)만 따져보면 뭐가 이득인지 궁금합니다.
그리고 알고리즘 문제를 풀 때, 동적할당은 피해야하는지도 궁금합니다.
감사합니다.
답변을 작성해보세요.
0
김태원
지식공유자2021.07.25
안녕하세요^^
소수의 개수를 구하는 방법은 위에 코드처럼 에라토스테네스체로 푸는게 가장 효율적인 코드입니다.
아래 코드처럼 수정하면 더 좋습니다.
#include <stdio.h>
int main()
{
//freopen("input.txt", "rt", stdin);
int N;
scanf("%d", &N);
bool* isPrime = new bool[N+1];
for (int i = 0; i < N+1; ++i)
isPrime[i] = true;
int cnt=0;
for (int i = 2; i < N+1; ++i){
if(isPrime[i]){
cnt++;
for (int j = 2 * i; j < N+1; j += i)
isPrime[j] = false;
}
}
printf("%d\n", cnt);
if (isPrime)
delete[] isPrime;
return 0;
}0
김태원
지식공유자2021.07.22
안녕하세요^^
코드르 위와 같이 올리시면 제가 볼 수가 없습니다. {;}버튼을 이용해서 올려주시면 감사하겠습니다.
동적할당은 하는게 좋습니다. 강좌 뒤로 가면 vector를 사용하면서 동적할당을 많이 합니다.
답변 2