C++ - (백준) 17425번 소수 구하기

0. 문제

www.acmicpc.net/problem/17425

17425번: 약수의 합

 

1. 문제 해석

1-1. 입력되는 값의 범위가 큼

: long long 타입 변수 사용, 숫자를 입력할 때마다 조건에 맞는 답을 하나하나 찾는 것은 하면 안됨 -> 미리 판단 후 판단 결과를 배열에 저장하는 방식 이용

 

2. 코드

#include <iostream>
#include <cstring>

long long M;
long long N;
int i;
int temp;

//bool ans[1000000]={true};
bool ans[1000000];


int main(){
    // 소수 이외의 숫자를 거르는 알고리즘 사용
    
    //배열 초기화
    memset(ans,true,sizeof(ans));
    scanf("%lld %lld",&M, &N);
    
    ans[1]=false;
    for(long long i=2; i<=N; i++){
        //2부터 하나씩 기준 숫자가 됨. 예1-1) i가 5일 때
        if(ans[i]){
            for(long long j=2*i; j<=N; j+=i){
                //예1-2) 5의 배수는 소수가 아니므로 제거
                ans[j]=false;
            }
        }

    }

    for(long long i=M; i<=N; i++){
        if(ans[i]==true) printf("%lld\n",i);
    }
    
}

 

3. 알아야 하는 것

3-1. 배열 초기화 

; cstring 라이브러리 이용한 memset 함수

 

3-2. 에라스토네의 체

: 어떤 수의 배수를 걸러내는 방법 ( 어떤 수의 배수는 소수가 아니기 때문 ex) 4는 2의 배수이므로 소수가 아님

-> 입력 받는 수의  범위가 1,000,000 까지로 매우 크기 때문에 입력 받을 때마다 한 숫자씩 소수가 맞는지 아닌지 확인하는 것은 매우 시간이 오래걸려서 시간초과가 된다. 따라서 배열에 각 인덱스에 해당하는 숫자들이 소수인지 아닌지 판별한 결과를 미리 넣어놓아야 한다.

-> for 문 2개로 배수 숫자들은 소수가 아니라는 것을 bool 배열에 넣어줌