소수 판단 함수(1)

소수인지 판단하는 함수를 작성하면, 

우선 가장 간단하게 생각하면 다음과 같다.

def is_prime(N):
    c = 0
    for i in range(2, N):
        if N % i == 0:
            c += 1
            break
    return c == 0
 
for numbers in range (2, 101):
    if(is_prime(numbers)):
        print(numbers)

주어진 수보다 작은 숫자들로 모두 나눠보고, 

나눠지는 수가 있다면 소수가 아니게 된다.

 

 

이 생각에서 한단계 나아가서 

어떤 수 N에 대해 N이 a*b로 나눠지는 수라면 

a와 b의 최대는 루트 N이라는 생각을 하면,

def is_prime(N):
    c = 0
    for i in range(2, int(N**0.5)+1):
        if N % i == 0:
            c += 1
            break
    return c == 0
 
for numbers in range (2, 201):
    if(is_prime(numbers)):
        print(numbers)
 

위와 같이 루트 N 이하의 값에 대해서만 나눠봐도 된다. 

 

 

마지막으로, 

정말 한단계 더 나아가서

이번에는 소수로만 수들을 나눠도 된다는 생각을 할 수 있다.

물론 이때도 루트 N 보다 작은 수들로만 나눠도 된다.

prime = [2]
def is_prime(N):
    c = 0
    for i in prime:
        if (N != 2 and N % i == 0):
            c += 1
            break
        if i > int(N**0.5)+1:
            break
    if (c==0 and N != 2):
        prime.append(N)
    return c == 0
 
for numbers in range (2, 1001):
    if(is_prime(numbers)):
        print(numbers)

이때 2가 소수임은 잘 알려진 사실이므로,

초기에 prime에 넣어주었고,

그 이후로는 append를 통해 소수들을 prime 리스트에 넣어주었다.