에라토스테네스의 체-소수 찾기, 1978번:소수 찾기, 프로그래머스 소수 찾기

소수 찾기 알고리즘 - 에라토스테네스의 체

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

설명이 자세히 나와있다.

 

위키백과에서 구현한 에라토스테네스의 체 코드 정리 (출처:위키백과)

#include <bits/stdc++.h>
using namespace std;

vector<bool> b(20000);
void Eratos(int n){ //n까지의 소수 구하기
    if(n<=1) return; //1일때는 소수 없음
    fill(b.begin(), b.end(), true); 
    b[0]=b[1]=false; //소수가 아닌 것은 false
    for(int i=2;i*i<=n;i++){ //2부터 n까지 탐색
        if(b[i]){ //소수이면
            for(int j=i*i;j<=n;j+=i){ //소수의 배수들 false 표시
                b[j]=false;
            }
        }
    }
}

int main(){
    Eratos(20); //1~20까지 소수 구하기
    for(int i=0;i<=20;i++){
        if(b[i]==true) cout << i << " ";
    }  
}

 

1978번: 소수 찾기

소수 찾기

 

시간 제한            메모리 제한            제출            정답            맞힌 사람            정답 비율

2 초

128 MB

160269

74881

59823

46.597%

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

 

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1 복사

4
1 3 5 7

예제 출력 1 복사

3

 

 

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<bool> b(1004);
int n, temp, cnt;
void Eratos(int n){ 
    if (n<=1) return;
    fill(b.begin(), b.end(), true);
    b[0]=false; b[1]=false;
    for(int i=2;i*i<=n;i++){
        if(b[i]){
            for(int j=i*i;j<=n;j+=i){
                b[j]=false;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    Eratos(1004);
    cin >> n;
    for(int i=0;i<n;i++){
        cin>>temp;
        if(b[temp]==true) cnt++;
    }
    cout << cnt;

}

 

 

소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

코드

#include <bits/stdc++.h>

using namespace std;
const int MAX=10000000;
int visited[MAX+1], arr[MAX+1], cnt;
string str;
set<int> ans;
void dfs(int count, string number, int total){
    if(count==total){ //문자열을 set에 저장하기
        ans.insert(stoi(str));
        return;
    }
    for(int i=0;i<number.size();i++){ //최대 크기만큼 만들기
        if(!visited[i]){
            visited[i]=true; //방문표시
            str.push_back(number[i]); //str의 끝에 char 붙이기
            dfs(count+1, number, total);
            //초기화
            str.pop_back();
            visited[i]=false;
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    //1. 문자열 만들기-dfs
    for(int i=1;i<=numbers.size();i++){ //크기별로 뽑기
        dfs(0,numbers,i);
    }
    //2. 에라토스테네스의 체
    fill(arr,arr+MAX+1, true);
    arr[0]=arr[1]=false;
    int max_value = *max_element(ans.begin(), ans.end());
    for(int i=2;i*i<=max_value;i++){
        if(arr[i]){
            for(int j=i*i;j<=max_value;j+=i){
                arr[j]=false;
            }
        }
    }
    //3. 정답 출력
    for(int a:ans){
        if(arr[a]==true) answer++;
    }
    
    return answer;
}

 

프로그래머스 - 소수 찾기 코드 참고사이트

문자열 만드는 것이 어려워서 이 분 블로그 코드 참고해서 풀었다.

https://kim519620.tistory.com/entry/%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-feat-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-42839%EB%B2%88

소수 찾기 (feat. 프로그래머스, 42839번)

 

int val = *max_element(arr,arr+size);

최대값 구하기

https://m.blog.naver.com/kks227/220246803499

[C++ 강좌] 093 - 알고리즘 헤더 파일 (2) - max_element(), min_element()

 

문자열 범위

문자열 범위가 안정해져서 작게 백만정도로 했는데 segmentation fault 오류가 발생했다.

10000000-천만 정도로 하자.