코테 연습[자바 코테 준비 6일차]

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

프로그래머스

간단한 단계를 거치면 된다.

 

1. k 진수 변환

자바  ->

String want =  Integer.toString(n,k) ;  // k 진수로 바꾸기

 2. 조건에 맞는 수 추리기 : 0 으로 split 

String[] numbers = want.split("0");

 

이후 소수 판별 :

https://myjamong.tistory.com/139

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

brutal 하기에는 비효율적일것 같으므로 , 루트 본인 수 까지 구하자.

 

어렵지는 않지만, 1 과 11 통과를 못한다.

1.

-> Int 자료 형들을 Long 으로 해주자.

 

2.  짝수 부분 확인과 홀수 부분의 확인을 분리하자,

홀수 를 확인시  다음과 같이 홀수 만 확인 하여 시간을 최대한 줄이자.

for (long i = 3; i * i <= num; i += 2) {
    if (num % i == 0) {
        return false;
    }
}

 

public int solution1_optimized(int n, int k) {
    String want = Integer.toString(n, k);  // Convert to base-k string

    String[] numbers = want.split("0");
    List<Long> primes = new ArrayList<>();

    for (String item : numbers) {
        if (!item.isEmpty()) {
            long num = Long.parseLong(item);
            if (isPrime(num)) {
                primes.add(num);
            }
        }
    }

    return primes.size();
}

private boolean isPrime(long num) {
    if (num < 2) {
        return false;
    }

    if (num == 2) {
        return true;
    }

    if (num % 2 == 0) {
        return false;
    }

    for (long i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}