#8 기본 수학2 - 1

백준 문제풀이

 

1978번 문제 : 소수 찾기

문제 :

 

소스코드 :

#include <iostream>

using namespace std;

int primeNum(int num) {
    int sum = 0;
    for(int i=1; i<=num; i++) {
        if (num % i == 0) {
            sum++;
        }
    }
    if (sum == 2) {
        return 1;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m, k;
    int count = 0;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> m;
        k = primeNum(m);
        count += k;
    }
    
    cout << count;
    
    return 0;
}

 

소수인지 아닌지 판별해서 소수이면 1을, 아니라면 0을 반환하는 함수 primeNum를 작성하여 사용했다.

 

 

2581번 문제 : 소수

문제 :

 

소스코드 :

#include <iostream>

using namespace std;

int primeNum(int num) {

    int sum = 0;
    for(int i=1; i<=num; i++) {
        if (num % i == 0) {
            sum++;
        }
    }
    if (sum == 2) {
        return num;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int m, n, k;
    bool firstPossible = true;
    int firstNum = 0;
    int result = 0;
    cin >> m >> n;
    
    for(int i=m; i<=n; i++) {
        k = primeNum(i);
        result += k;
        if ((k > 0) && (firstPossible == true)) {
            firstPossible = false;
            firstNum = i;
        }
    }
    
    if (firstPossible == true) {
        cout << "-1";
    }
    else {
        cout << result << "\n" << firstNum;
    }

    return 0;
}

 

 

11653번 문제 : 소인수분해

문제 :

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> v;

int primeNum(int num) {
    int sum = 0;
    for(int i=1; i<=num; i++) {
        if (num % i == 0) {
            sum++;
        }
    }
    if (sum == 2) {
        return 1;
    }
    return 0;
}

void fact(int a) {
    
    if (primeNum(a)) {
        v.push_back(a);
        return;
    }
    for(int i=2; i<=a; i++) {
        if (a % i == 0) {
            v.push_back(i);
            a = a / i;
            return fact(a);
        }
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    
    fact(n);
    
    for(int i=0; i<v.size(); i++) {
        cout << v[i] << "\n";
    }

    return 0;
}

 

함수와 재귀함수, 전역변수를 사용해보고 싶어서 이렇게 장황하게 구현해보았다.

간단하게 구현하는건 다음과 같이 while true를 사용해서 n이 1이 될 때 까지 무한반복시키면 된다.

 

#include <iostream>

using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;

    while(true) {
        if (n == 1) break;
        for(int i=2; i<=n; i++) {
            if (n % i == 0) {
                cout << i << "\n";
                n = n / i;
                break;
            }
        }
        
    }
    return 0;
}

 

 

 

1929번 문제 : 소수 구하기

문제 :

 

 

소스코드(시간초과) :

// 시간 초과된 소스 코드입니다.
#include <iostream>

using namespace std;

int primeNum(int a) {
    int cnt = 0;
    for(int i=1; i<=a; i++) {
        if (a % i == 0) {
            cnt++;
        }
    }
    if (cnt == 2) {
        return a;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int m, n;
    cin >> m >> n;
    
    for(int i=m; i<=n; i++) {
        if (primeNum(i) > 0) {
            cout << primeNum(i) << "\n";
        }
    }
    
    return 0;
}

 

제출해도 채점이 엄청 오래 걸리길래 백준 서버에 렉이 걸린 줄 알았다..

기다려보니 시간초과가 떴다.

다시 문제를 잘 보니 (1 ≤ M ≤ N ≤ 1,000,000) 조건을 간과했다.

이러면 시간 초과가 당연한 수순이다.

그래서 N이 클 경우 소수를 찾는데 시간을 효과적으로 줄이는 법을 검색하여 학습하기로 했다.

 

 

 

소수 구하기 - 에라토스테네스의 체 방법

 

2부터 시작해서 해당 수 제외한 해당 수의 배수들을 제거하는 방법이다.

그냥 for문을 돌리면 n에 따라 소수를 찾는게 많은 시간이 소요되어 시간 초과가 발생할 수 있다.

에라토스테네스의 체 방법을 이용하면 시간을 줄일 수 있다.

 

 

1929번 소수 구하기

소스코드 :

#include <iostream>

using namespace std;

#define size 1000001
int a[size] = {0,1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int m, n;
    cin >> m >> n;
    
     // 2*2, 2*3, 2*4 ... 3*2, 3*3, 3*4, ... 4*2, 4*3 ..
    for(int i=2; i<=n; i++) {
        for(int j=2; i*j<=n; j++) {
            a[i*j] = 1;
        }
    }
    for(int i=m; i<=n; i++) {
        if (a[i] == 0) cout << i << "\n";
    }

    return 0;
}