[C++] BOJ 4969: 월요일-토요일

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

 

[English] -> Click on the [영어] button on the side

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
    int nums[300001]={};
    fill(nums,nums+300001,0);
    for (int i=2;i<300000+1;i++){
        if (i%7==1 || i%7==6){
            nums[i]=1;
        }
    }
    for (int i=2;i<sqrt(300001)+1;i++){
        if (nums[i]){
            for (int j=2*i;j<300001;j+=i)
                nums[j]=0;
        }
    }
    while (1){
        int n;
        cin>>n;
        if (n==1) return 0;
        vector <int> answer={};
        for (int i = 2; i <= sqrt(n); ++i) {
            if (n % i == 0) {
                if (nums[i]) answer.push_back(i);
                if (i != n / i && nums[n / i]) answer.push_back(n / i); 
            }
        }
        if (nums[n]) answer.push_back(n);
        sort(answer.begin(),answer.end());
        cout<<n<<": ";
        for (int i=0;i<answer.size();i++){
            cout<<answer[i]<<" ";
        }
        cout<<"\n";
    }
}

 

해당 문제는 에라토스테네스의 체의 변형을 이용하여 풀었다.

먼저, 숫자의 최대 사이즈인 30만을 배열로 저장하여, 월요일-토요일 소수 여부를 파악하였다.

월요일-토요일 소수는 1, 아닌 수는 0으로 저장했다.

월요일-토요일 소수가 되기 위해서는 7로 나누었을때 1 혹은 6의 나머지가 나와야하기에, 먼저 이 조건을 만족시키는 모든 숫자들을 1로 설정하였다. 이 숫자들은 월요일-토요일 소수가 될 수 있는 숫자들이다.

이후 월요일-토요일 소수가 될 수 있는 숫자들을 대상으로 에라토스테네스의 체의 성질을 이용하여, 해당 숫자의 배수들은 월요일-토요일 '소수'가 될 수 없기에 제외해주는 방식으로 월요일-토요일 소수를 저장했다.

이후 input으로 들어온 숫자보다 작은 월요일-토요일 소수들을 확인하였는데, 마지막으로 자기 자신 또한 월요일-토요일 소수일 수 있기 때문에 확인해주었다.