프로그래머스 k진수에서 소수개수구하기 c++ //core dumped 해결방법, 소수판별알고리즘, k진법 변환 알고리즘

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

프로그래머스

1. k진법 변환 알고리즘

//n을 k진수로 바꿈
string go(ll n,ll k){
    string ret="";
    while(n>=k){
        ret+=to_string(n%k);
        n/=k;
    }
    ret+=to_string(n);
    reverse(ret.begin(),ret.end());
    return ret;
}

2. 소수판별알고리즘

에라스토테네스하면 시간초과 난다...

이게 최적인듯?

// 소수 판별 함수
int isprime(ll n){
    if(n<=1) return 0;
    for(ll i=2;i<=sqrt(n);++i){
        if(n%i==0) return 0;
    }
    return 1;
}

 

3. core dumped 해결방법

1. type을 long long 으로 바꾸기

2. stoi, stol 하기전에 string의 size가 있는경우만 실행 

//if(temp.size() && stol(temp)) {~~~}

 

4. 전체코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int ret;
vector<int> primes;
// 소수 판별 함수
int isprime(ll n){
    if(n<=1) return 0;
    for(ll i=2;i<=sqrt(n);++i){
        if(n%i==0) return 0;
    }
    return 1;
}
//n을 k진수로 바꿈
string go(ll n,ll k){
    string ret="";
    while(n>=k){
        ret+=to_string(n%k);
        n/=k;
    }
    ret+=to_string(n);
    reverse(ret.begin(),ret.end());
    return ret;
}
// int isPrime(int n){
//     if(n==1) return 0;
//     if(n==2) return 1;
//     for(int i=3;i<sqrt(1000000);++i){
//         if(n%(i+1)==0) return 0;
//     }
//     return 1;
// }
int solution(int n, int k) {

    string s= go(n,k);
    
    cout<<s<<"\n";
    string temp="";
    for(int i=0;i<s.size();++i){
        if(s[i]!='0'){
            temp+=s[i];
            continue;
        }
        if(s[i]=='0'){
            if(temp.size()){ //이래야 런타임에러안남!
                cout<<stol(temp)<<" ";
                if(isprime(stol(temp)))ret++;
            }
            temp="";
        }
    }
    cout<<temp<<" "; //뒤에남은애
    if(temp.size() && isprime(stol(temp))) ret++;
    
    return ret;
}