[Lv 2] 숫자 블록

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

프로그래머스

 

이 문제는 소수를 찾는 문제이다.

n번째 블록의 놓여질 숫자는 소수인 경우 1을 배치하고, 아닌 경우 10,000,000보다 작은 제일 큰 약수이다.

 

약수를 구할 때는 제곱근 방식을 사용해서 실행 시간을 절약해야한다.

n이 1인 경우는 0이 적힌 블록이 있어야하므로, 이 부분만 예외처리해준다.

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int isPrime(int n) {
    if (n < 2) return 0;

    int max = 0;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            max = i;
            if (n / i <= 10000000) return n / i;

        }
    }

    if (!max) return 1; // 소수
    else return max;
}

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    for (long long i = begin; i <= end; i++) {
        answer.push_back(isPrime(i));
    }
    return answer;
}