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

소수(Prime Number)

소수는 자신보다 작은 두개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
ex) 5는 5*1 또는 1*5로 수를 곱합 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다.

소수 (수론) - 위키백과, 우리 모두의 백과사전

2, 3, 5, 7, 11 ... 등 1과 자기 자신만을 약수로 갖는 수를 소수라고 한다.

 

소수 판별하기 알고리즘

기본적으로 소수를 판별하는 방법은 어느 수까지 판별하는 수를 나눠서 나머지가 0이 안나오면 소수로 인정한다. 가장 효율적인 방법을 찾기 위해 절차적으로 풀이를 확인해보자.

 

풀이1

첫번째 풀이는 2부터 판별하는 수 전까지 나눠보고 나머지가 0이 안나온다면 소수로 정의한다. 해당 수까지 모두 확인해야하므로 시간복잡도는 O(N)이 되고, 가장 원초적인 방법이다.

public class Main {
    public static boolean isPrime(int num){
        for(int i=2; i<num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
    public static void main(String[] args) {
       System.out.println(isPrime(80));
       System.out.println(isPrime(79));
    }
}

 

풀이2

두번째는 해당숫자의 절반까지만 확인하는 방법이다. 이 원리는 절반 이상의 숫자들은 확인이 필요 없는 숫자들이기 때문이다. 예를들어 80이란 숫자에서 자기자신을 제외하고 절반을 초과하는 숫자에서 나눴을때 나머지가 0이되는 숫자는 나올수가 없다. 해당 풀이를 사용하면 최대 N/2번 조회를 한다. 시간복잡도에서 상수는 제외하므로 해당 풀이의 시간복잡도도 O(N)이 된다.

public class Main {
    public static boolean isPrime(int num){
        for(int i=2; i<=num/2; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
    public static void main(String[] args) {
       System.out.println(isPrime(80));
       System.out.println(isPrime(79));
    }
}

 

풀이3

마지막 풀이는 두번째 풀이의 원리를 조금 인용해서 소수를 판별하는 가장 효율적인 방법이라고 생각한다. 해당 숫자의 √N 까지 확인하는 방법이다. 이 원리는 약수의 중심을 구하는 방법이다. 예를들어 80의 약수는 아래와 같다.

1, 2, 4, 5, 8, 10, 16, 20, 40, 80

각 숫자들의 곱이 80이되는 쌍을 같은 색으로 표시했다. 1:80, 2:40, 4:20, 5:16, 8:10. √80의 값은 대략 8.xxx의 값이 나온다. 즉 약수들의 곱으로 봤을때 루트를 씌운 값이 중간값이 된다. 이 원리는 이용하여 2에서부터 √N의 값까지 검색을한다며 이후의 값은 확인할 필요가 없게 된고 시간복잡도는 O(√N)이 된다. 코드의 가독성을 위해 루트함수는 사용하지 않고 i의 제곱값으로 확인을한다.

public class Main {
    public static boolean isPrime(int num){
        for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
    public static void main(String[] args) {
       System.out.println(isPrime(80));
       System.out.println(isPrime(79));
    }
}

 

 

백준 1978번 문제 :: 소수 찾기

1978번: 소수 찾기

풀이

소수를 구하는 메소드를 함들어서 소수인지 하나씩 확인한다.

 

Java

import java.util.Scanner;
 
public class Main{
    public static boolean isPrime(int num){
        if(num < 2) return false;
        for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;            
        }
        return true;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int result = 0;
        for(int i=0; i<T; i++){
            int num = sc.nextInt();
            if(isPrime(num)) result++;
        }
        System.out.println(result);
    }
}