백준 1929번: 소수 구하기 [C++]

코드

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int main(){
    int m, n;
    
    scanf("%d %d", &m, &n);
    
    bool* p_arr = new bool[n+1];
    
    for(int i=0; i<n+1; i++)
        p_arr[i] = true;
    
    int temp = sqrt(n)+1;
    p_arr[1] = false;
    for(int i=2; i<temp; i++){
        if(p_arr[i])
            for(int j=i*i; j<= n; j+=i){
                p_arr[j] = false;}
        
    }
                
    for(int k=m; k<=n; k++){
        if(p_arr[k]){
            printf("%d\n", k);
            }
           
    
    }
    delete[] p_arr;
}

 

풀이

아무래도 코딩 능력이 갈수록 떨어지는것 같다...

이번에 그냥 아무생각없이 에라토스테네스의 체라고 만들어서 문제를 풀었는데, 정작 진짜 에라토스테네스의 체를 사용해야하는 이번문제에서 시간초과가 뜨길래 1년전 꽤 빠른시간에 통과한 코드는 어떻게 해서 했나 봤더니...

지금은 귀찮아서 하라해도 안하는 가변 배열도 사용하고 야무지게 메모리 해제도 해준것도 모잘라서

에라토스테네스를 제대로 썼었다. 거기에다 입출력도 성능이 떨어지는 cout cin 이 아니라 scanf와 prinf를 써 주는 모습까지... 1년전 C++ 수업을 들었을때라 그런거였겟지?

https://wonsang98.tistory.com/185

백준 1978번: 소수 찾기 [C++]

https://wonsang98.tistory.com/186

백준 2581번: 소수 [C++]

생각해보니 어차피 이전 자연수에서 배수로 지워지지 않았다는것 자체가 소수라는 것이기때문에

소수 판별을 따로 할 필요가 없었는데, 나는 이상하게 에라토스테네스의 체 개념을 쓰면서 소수 판별함수도 동시에 기용해서 소수 판별 함수로만 판별하는것보다는 빠르지만... 에라토스테네스의 체를 제대로 사용하는것보다는 훨씬 느린 이상한 방법으로 문제를 계속 풀어왔던것이다.

따라서 제대로 사용했다면 2부터 시작해서 그 수 자체는 놔두고 배수만 지워주고, 수가 올라가면서 그걸 반복하면 되는거였는데... 좀 안다고 생각해서 그냥 짚이는 대로 풀었더니 이런 참사가 발생한것 같다.