소수 구하기

N 이하의 소수를 모두 출력하시오.

소수: 1보다 큰 자연수 중 1과 자기 자신만 약수로 가지는 수 

 

처음 생각했던 방법:

def find_prime_list_under_number(number):
    prime_list = []
    for num in range(number + 1):
        isPrime = True
        if num <= 1:
            continue
        for i in range(2, num):
            if num % i == 0:
                isPrime = False
        if isPrime:
            prime_list.append(num)
    return prime_list

 

1. N 까지 for-loop 돌면서:

2. 자기 자신만 약수로 가지는지 (즉, 2부터 자기 자신까지 Modulo operation 을 돌렸을 때 0이 나오는지, 아닌지) 확인  

3. isPrime 이라는 플래그를 이용해서, 소수이면 반환할 리스트에 저장.

 

- 단점: Brute-force 방식이라, 숫자가 커지면 무리가 있음.

 

 

개선: 

import math

def find_prime_list_under_number(number):
    prime_list = []
    
    for num in range(2, number + 1):
        for i in range(2, int(math.sqrt(num) + 1):
            if num % i == 0:
            	break
        else:
        	prime_list.append(num)
    return prime_list

 

1. 1을 제외한 N 까지 for-loop을 돌면서:

2. 약수는 대칭이기에 루트 N 까지만 검사하여, inner for-loop 에서 검사 횟수를 줄임

3. for-else 문을 이용하여 mod 연산이 0이 아니면(즉, break 가 실행되지 않았을 때), else 가 실행되서 반환 리스트에 저장.

 

 

다시 개선:

def find_prime_list_under_number(number):
    prime_list = []
    
    for num in range(2, number + 1):
        for i in prime_list:
            if i * i <= num and num % i == 0:
            	break
        else:
        	prime_list.append(num)
    return prime_list

 

1. 소수의 곱으로 만들어진 합성수는 굳이 검사할 필요가 없으니까, 구했던 소수 리스트로만 inner for-loop을 돈다.

- ie. 2 또는 3으로 나누어 떨어지지 않는 수인데, 그 둘을 곱한 6으로 나누어떨어질리가 없다.

2. num이 소수가 아니라, num = a * b 처럼 나누어 떨어지는 수라면:

- a, b 둘 중 하나는 반드시 num^1/2 이하다.

 

예시:

- num = 36

- 약수 쌍: (1,36), (2, 18), (3, 12), (4, 9), (6, 6), ...

- 36^1/2 = 6에서 중간이고, 그 이후부터는 거꾸로 뒤집힌것 뿐

-> 그래서, 

- i * i > num이 되는 순간부터는,

- i 보다 큰 수와의 곱만 남게 되므로

- 이미 그 이전에 약수 쌍의 작은 수는 다 검사한 것이다.

 

 

문제 링크: https://www.acmicpc.net/problem/1929