소수 판별 알고리즘

소수 판별 알고리즘

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

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("소수 입니다"); } } } }

from http://art-coding3.tistory.com/33 by ccl(A) rewrite - 2021-09-19 12:27:51