인프런 커뮤니티 질문&답변
작성한 질문수
제가 짠 코드는 비효율적인 코드일까요?
작성
·
255
0
9번 모두의 약수 문제를 참고하여 메모리에 저장하는 방식으로 코드르 짜보았습니다.
int main()
{
//freopen("input.txt", "rt", stdin);
int a=0;
int aa[200000]={0,};
aa[0]=1;
aa[1]=1;
cin >> a;
for(int i=2; i<a; i++){
for(int j=i*2; j<a; j+=i){
aa[j]=1;
}
}
int cnt=0;
for(int i=0; i<a; i++){
if(aa[i]!=1){
cnt++;
}
}
a==2 ? cout << 1 : cout << cnt;
return 0;
}
답변 2
0
입력이 2뿐이 아니라 소수가 입력되는 상황도 있었네요.
이중for문 하나로 cnt까지 카운트 하는 방법이 있을 줄은 몰랐네요. 새로운 방법 알아갑니다.
빠른 답변과 자세한 설명 감사합니다!
0
9번을 배우고 응용해서 15번을 이렇게 생각해서 풀었다는게 대단하네요.
이 방법은 메모리 낭비가 조금 있지만 소수의 개수를 구하는 방법중에서는 가장 빠른 방법입니다. 200,000만 크기는 그리 크지 않으니 선택해도 좋을 것 같습니다.
위 코드는 N이 19와 같은 소수가 입력되면 마지막 소수를 카운드하지 않는 코드이니 참고하세요.
참고로 수학에서 소수들을 구하는 방법중에 "에라토스테네스의 체" 라는 방법이 있습니다. donald010님이 짜신 방법이 그와 매우 유사합니다. 아래 코드는 "에라토스테네스의 체" 방식으로 짜본 것입니다. donald010님이 짜신것과 비교해보시면 좋을 것 같습니다.
#include<iostream>
#include<vector>
using namespace std;
int main(){
//freopen("input.txt", "rt", stdin);
int n, cnt=0;
cin>>n;
vector<int> ch(n+1);
for(int i=2; i<=n; i++){
if(ch[i]==0){
cnt++;
for(int j=i; j<=n; j+=i) ch[j]=1;
}
}
cout<<cnt;
return 0;
}