[알고리즘] 소수 판별

※ 사용 언어 : 자바, 파이썬

 

 

 

1. O(N) 시간 복잡도의 소수 판별

• 소수인지 판별할 수 N의 이전 값(=N-1)까지 2부터 for 문을 돌리는 방식이다.
• 해당 알고리즘은 N의 값 만큼 돌아간다.

 

『파이썬』

N=int(input())

if(N<2):
    print("소수가 아닙니다")
    
else:
    flag=False 
    for i in range(2,N-1):
        if(N%i==0):
            print("소수가 아닙니다")
            flag=True # N은 결국 소수가 아니다
            break
            
    if(flag==False): 
    	# N이 소수 일때, print문 출력을 위해 flag 변수를 두어
        # N이 소수가 아닐 때 flag=True로 바꿈.
        print("소수 입니다")

『자바』

import java.util.Scanner;
public class PrimeNumber {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        boolean flag = false;
        if (N < 2) {
            System.out.println("소수가 아닙니다");
        }
        else {
            for (int i = 2; i < N; i++) {
                if (N % i == 0) {
                    flag = true;
                    System.out.println("소수가 아닙니다");
                }
            }
            if (flag == false) { 
            // 소수가 아닐 경우 출력문을 만들기 위해서 flag 사용
                System.out.println("소수 입니다");
            }
        }
    }
}

 

 

---

 

 

2. O(√N) 시간 복잡도의 소수 판별

• √N 이전의 수에서 N과 나눠떨어지지 않으면 N은 소수라는 점에서 착안하여 나온 알고리즘이다

가령― N=40일때, 40의 약수는 【 1 2 4 5 8 10 20 40 】이다. 약수를 쌍으로 묶으면, 【 1 40 】 【 2 20 】 【 4 10 】 【 5 8 】이다.    묶은 값의 제일 앞 값 중에 가장 큰 수는 5이다.   그리고 √40은 6.342…이며, 5 < √40이다. 즉 N이 소수가 아니라면 √N 전에 N의 약수가 등장한다는 점을 이용한 것이다. 보통 루트 계산이 어렵기 때문에 제곱근으로 바꿔서 계산한다. 즉 N과 나눌 i 값을 제곱하고 N과 비교한다 ▶ i*i <= N

 

『파이썬』

N=int(input())

if(N<2):
    print("소수가 아닙니다.")
else:
    i=2
    flag=False
    while i*i<=N:
    # i*i <= N 은
    # i <= √N 과 동일하다
        if(N%i==0):
            print("소수가 아닙니다")
            flag=True
            break
        i+=1
    if(flag==False):
        print("소수 입니다.")

『자바』

import java.util.Scanner;
public class PrimeNumber {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        boolean flag = false;

        if (N < 2) {
            System.out.println("소수가 아닙니다");
        }
        else {
            for (int i = 2; i*i <= N; i++) {
                if (N % i == 0) {
                    flag = true;
                    System.out.println("소수가 아닙니다");
                }
            }
            if (flag == false) {
                System.out.println("소수 입니다");
            }
        }
    }
}