파이썬 소수 나열하기

파이썬 소수 나열하기

소수란 1과 자기 자신 이외의 정수로 나누어 떨어지지 않는 수를 의미합니다.

 

즉 1과 자기 자신 이외의 정수로 나누어 떨어진다면 소수가 아님을 알 수 있습니다.

이를 통해 작성한 코드는 아래와 같습니다.

cnt = 0 # 곱셈과 나눗셈을 합한 횟수
ptr = 0 # 이미 찾은 소수의 갯수
prime = [None] * 500 # 소수를 저장할 배열

prime[ptr] = 2 # 2는 소수이기에 미리 지정한다.
ptr += 1

for n in range(3, 1001, 2): # 짝수는 확실한 합성수이므로, 5부터 1000까지 홀수만 대상으로 반복
    for i in range(1, ptr):
        cnt += 1
        if n % ptr[i] == 0: # n이 소수로 나누어지면, 합성수이므로 break 문을 통해 빠져나간다.    
            break
        
    else: # n이 소수로 나누어지지 않는다면 소수 배열에 추가해준다.
        prime[ptr] = n
        ptr += 1

for i in range(ptr):
    print(ptr[i])

 

약수를 구할 때

만약 100의 약수를 구한다고 치면

2 * 50

4 * 25

5 * 20

20 * 5

25 * 4

50 * 2

이러한 약수들이 나올 것입니다

 

여러분은 위 약수들의 특징에 대해 눈치 채셨나요???

 

특징은 바로 "대칭성" 입니다!

 

2 * 50

4 * 25

5 * 20

 

와

 

20 * 5

25 * 4

50 * 2

 

이 서로 대칭을 이룬다는 것인데요. 

즉 계산을 할 때 절반만 계산을 해도 같은 의미라는 뜻입니다!

2 * 50

4 * 25

5 * 20

20 * 5

25 * 4

50 * 2

 

 

이를 통해 소수를 구할 때 숫자가 본인의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않으면 소수임을 구하는 알고리즘을

만들어 위 코드의 연산 횟수를 더 줄일 수 있습니다!

cnt = 0 # 곱셈과 나눗셈을 합한 연산 횟수
ptr = 0 # 이미 찾은 소수의 갯수
prime = [None] * 500 # 소수를 저장할 배열

prime[ptr] = 2 # 2는 소수이기에 미리 지정한다.
ptr += 1

prime[ptr] = 3 # 3은 소수이기에 미리 지정한다.
ptr += 1

for n in range(5, 1001, 2): # 짝수는 확실한 합성수이므로, 5부터 1000까지 홀수만 대상으로 반복
    i = 1
    while prime[i] * prime[i] <= n: # prime[i]가 n의 제곱근보다 작으면 종료
        cnt += 2
        if n % prime[i] == 0: # n이 소수로 나누어지면 합성수이므로 break
            break
        i += 1
    else: # 나누어 떨어지지않는다면 소수이므로 배열에 추가해준다.
        prime[ptr] = n 
        ptr += 1
        cnt += 1 # 연산 횟수 1을 더해준다.

 

 

Devide & Conquer

while prime[i] * prime[i] <= n: # prime[i]가 n의 제곱근보다 작으면 종료
        cnt += 2

• n의 제곱근을 구하는 것보다 prime[i]를 제곱으로 만드는게 더 쉽기에 위와 같이 하였습니다
• cnt는 곱셈과 나눗셈을 합한 횟수를 의미하기에 곱셈이나 나눗셈시 2를 더해줍니다.