Running Time And Complexity ( Prime number checker )

hackerrank 튜토리얼 문제입니다.

 

주어진 숫자 Number가

소수일        경우 : "Prime"

소수가 아닐 경우 : "Not prime"

문자열을 출력

 

가능하다면 소수연산 알고리즘 혹은 어떤 종류의 최적화를 통해 O(n)을 O(√n) 으로 최적화 하도록 쓰여 있습니다.우선 최적화는 생각하지 않습니다.

 

[ 제약 조건 ]

• 1 <= T <= 30
• 1 <= Number <= 2 * 10^9  (20억)

[ 입력 예시 (sample input) ]

// 편의를 위해 Scanner가 아닌 정적배열로 선언 하겠습니다.
int[] array = {12, 5, 7}

 

[ 출력 예시 (sample output) ]

Not prime
Prime
Prime

 

[ 해설 ]

• 12  ▶ 1과 12 이외에 { 2, 3, 4, 6 } 으로 나뉘어 집니다.  ▶ "Not prime"
• 5    ▶ 1과 5 이외에 다른 숫자로 나뉘어지지 않습니다. ▶ "Prime"
• 7    ▶ 1과 7 이외에 다른 숫자로 나뉘어지지 않습니다. ▶ "Prime"

 

먼저 주어진 정수배열을 순회하며, 소수인지 확인하는 메소드를 선언합니다.

public static boolean isPrime(int number) {
    return true;
}

public static void main(String[] args) {
    int[] array = { 12, 5, 7 };
    int size = array.length;
    for (int i = 0; i < size; i++) {
        if (isPrime(i))
            System.out.println("Prime");
        else
            System.out.println("Not prime");
    }
}

 

• 해설 내용을 잘 보면 정수 1과 자기자신으로 나뉘어지면 소수라는것을 알 수 있습니다.
• 1은 소수가 아니므로, false를 return 합니다.

public static boolean isPrime(int number) {
    if (number <= 1)
        return false;

    return true;
}

 

 

• 정수 1과 자기자신을 제외하고 나머지 연산을 수행합니다.
  2 <= i < number
• 나머지가 0이라는 것은 소수가 아니므로, false를 return 합니다.
• 주어진 정수에 대해 O(n) 만큼의 연산을 수행합니다.

public static boolean isPrime(int number) {
    if (number <= 1)
        return false;

    for (int i = 2; i < number; i++) {
        if (number % i == 0)
            return false;
    }
    return true;
}

 

 

• 하지만 위에 코드는 number의 숫자가 크면 클 수록, 연산 수행이 늘어난다는 단점이 있습니다.
• isPrime 메소드에 주어진 정수 number에 대하여 몇번 연산을 했는지와
  메소드 수행 완료시간을 측정해보겠습니다.

public static boolean isPrime(int number) {
    if (number <= 1)
        return false;

    int roopCount = 0;
    for (int i = 2; i < number; i++) {
        roopCount++;
        if (number % i == 0)
            return false;
    }
    System.out.println(number + " => RoopCount: " + roopCount);
    return true;
}

public static void main(String[] args) {
	long now = System.currentTimeMillis();
    isPrime(1073741831);
    System.out.println((System.currentTimeMillis() - now) / 1000.0);
}

 

output

1073741831 => RoopCount: 1073741829
2.274

반복문은 1073741829(10억)회 수행하여, 매개변수 number가 소수라는것을 알아 내었습니다.

수행시간은 제 PC기준 약 2초

저 또한 위와 같은 매개변수로 인해 Test Case에서 수행시간 제한초과 판정을 받았습니다.

 

문제를 다시 읽어보면, 가능하다면 수행시간을 O(n) => O(√n) 으로 줄여보라고 했었는데요

 

O(n) => O(√n)

isPrime(int number) => isPrime(int √number) 

저는 한참 쳐다봐서 수행시간을 정수에서, 정수의 제곱근만큼 줄여보라는 이야기로 해석 했습니다.

Java에서는 제곱근을 구하기 위해, Math.sqrt(double) 메소드를 제공합니다.

이 메소드를 사용하여 코드를 수정하겠습니다.

 

public static boolean isPrime(int number) {
    if (number <= 1)
        return false;

    Double d = Math.sqrt(number);
    int sqrt = d.intValue();
    for (int i = 2; i <= sqrt; i++) {
        if (number % i == 0)
            return false;
    }
    return true;
}

 

• Bad TestCase의 매개변수 1073741831(10억) 정수의 제곱근은 부동소수점 32768.00010681152 입니다.
• 부동소수점 32768.00010681152 을 int 타입으로 변환하면 32768입니다.
• 구한 제곱근값을 반복문의 최대범위로 지정하면, 반복 수행회수가 10억번에서 3만번으로 줄게 됩니다.
  
  

 

전체 코드

public class RunningTimeAndComplexity {

    // O(root of number)
    public static boolean isPrime(int number) {
        if (number == 1)
            return false;
        int sqrt = (int) Math.sqrt(number);
        for (int i = 2; i <= sqrt; i++) {
            if (number % i == 0)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] array = { 12, 5, 7 };
        // int[] array = { 1000000007, 100000003, 1000003 };
        int size = array.length;

        for (int i = 0; i < size; i++) {
            int number = array[i];
            if (isPrime(number))
                System.out.println("Prime");
            else
                System.out.println("Not prime");
        }
    }
}

 

 

[Github] URL

https://github.com/oracle8427/algorithm/blob/main/src/main/java/study/hacker_rank/RunningTimeAndComplexity.java

oracle8427/algorithm