Prime Number 여부 확인(단순탐색)

소수(Prime Number)는 1이외에 어떠한 값으로도 나눠지지 않는(나머지가 없는) Number를 의미합니다.

 

이런 소수는 암호악에서 주로 사용되며, 매우 큰 Number가 소수인지

 

소수가 아니면 어떻 값과 곱해지는지를 사용하는 방법이 사용됩니다.(공개키 암호)

 

컴퓨터가 해당 Number가 소수인지, 소수가 아니면 어떤 값과 곱해지는지 확인하는 방법은

 

1. 1~Number까지 나눠서, 나눈 나머지를 확인한다

1_1. 만약 나머지가 0이면 1 이외에 나눠지는 값이 있으므로, 소수가 아님

2. Number의 1/2까지 진행 후 알고리즘 종료

 

Number의 1/2를 넘어가면, 어차피 Number를 나눠도 1보다 작아지기 때문에 의미가 없습니다.

 

이렇게 되면 O(1/2N) = O(N)의 시간복잡도를 갖는 Prime Number 여부를 확인할 수 있게 됩니다.

 

import math
def isprime(number):
    #2부터 Number의 1/2값까지 반복문 실행
    for i in range(2, math.ceil(n/2)+1):
    	#number는 나눈 값이 나머지가 0인경우 Prime Number가 아님
        if divmod(number,i)[1] == 0:
            return i, False
            break
    return True
        
isprime(191)   
==> True

isprime(191191)   
==> 7, False

 

하지만 하나의 값이 소수인지만 찾으면 모를까, 다수의 값의 소수 여부를 판단하기에는

효율이 너무 좋지 못합니다.

효율성을 높히는 방법으로 에라토스테네스의 체 의 포스팅입니다.

https://teus-kiwiee.tistory.com/90

소수 찾기