Python에서 소수를 찾는 다양한 방법 분석

<시간/>

소수는 1 또는 자기 자신으로만 나누어 떨어지는 양의 정수입니다. 숫자가 소수인지 여부를 찾는 것은 오랫동안 흥미로운 프로그래밍 과제입니다. 게다가 방법도 다르고 효율도 다릅니다. 이 기사에서는 이러한 세 가지 방법을 살펴보고 실행 시간 측면에서 어떤 방법이 더 효율적인지 판단합니다.

모든 제수 확인

이것은 1에서 주어진 숫자보다 1이 작은 모든 정수를 취하고 숫자가 이들 중 하나로 나누어지는지 계속 확인하는 간단한 프로그램입니다. 이 숫자를 나눌 수 있는 숫자가 없으면 그 숫자가 소수입니다.

예시

import time
#Function to check Prime Number
def check_prime(final_val):
   if final_val <= 1:
      return False
   for divisor in range(2,final_val):
      if final_val % divisor == 0:
         return False
      return True
# Track the Start Time
StartTime = time.time()
#Count the number of prime numbers
cnt = 0
for final_val in range(1,10001):
   x = check_prime(final_val)
   cnt += x
print 'Count of prime numbers till',final_val,'is ', cnt
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

출력

위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -

Count of prime numbers till 10000 is 1229
Time Elapsed is: 2.3100001812

제곱근(N)까지의 인수

수학적으로는 우리가 검사하는 숫자의 제곱근까지 요인을 찾는 것으로 충분하다는 것도 발견되었습니다. 이 접근 방식은 반복 횟수를 줄이므로 아래와 같이 더 빠르게 확인할 수 있습니다. 이 아이디어를 구현하는 논리는 다음과 같습니다.

소수를 확인하고 있는 숫자의 제곱근을 찾습니다.
나머지가 남아 있는지 확인하기 위해 값 2부터 시작하여 제곱근 값까지 각 값으로 숫자를 나눕니다.
위의 단계에서 나머지 왼쪽이 0이면 숫자는 소수가 아닙니다.

예시

import math
import time
def is_prime(final_val):
   # 1 is not a prime number
   if final_val <= 1:
      return False
   i = 2
   while i <= math.floor(math.sqrt(final_val)):
   # Check if any remainders are cerated
      if final_val % i == 0:
         return False
      i += 1
   return True
# Track the Start Time
StartTime = time.time()
cnt = 0
for n in xrange(1, 10001):
   x = is_prime(n)
   cnt += x
print 'Count of prime numbers till',n,'is ', cnt
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

출력

위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -

Count of prime numbers till 10000 is 1229
Time Elapsed is: 0.0529999732971

에라토스테네스의 체

이 방법에서는 소수가 아닌 숫자나 합성 숫자를 제거하여 특정 숫자까지 소수를 얻습니다. 이를 달성하기 위해 따라야 할 단계는 다음과 같습니다.

2부터 모든 소수를 찾고자 하는 숫자까지 연속적인 정수 목록을 만드세요.
첫 번째 숫자, 즉 2를 가져와 모든 배수의 목록을 만듭니다. 원래 목록에서 이 배수 목록을 제거하지만 2는 제거하지 마십시오. 다음 숫자에 대해 이 작업을 반복합니다. 즉, 다음 숫자에 대해 3 등입니다. 숫자 자체가 아닌 배수만 제거한다는 점에 유의하십시오. 따라서 5 또는 11은 제거되지 않지만 10 및 22는 제거됩니다.
모든 제거 후 남은 목록은 요청된 숫자까지의 소수 목록입니다.

예시

import time
def sieve_method(n):
#Create a list of prime numbers
   prime_number_list = []
   for i in range(2, n+1):
# Capture the number if it si not in prime list
   if i not in prime_number_list:
      print (i)
# Add the number to the prime list number if it is a multiple
   for j in range(i*i, n+1, i):
      prime_number_list.append(j)
# Track the Start Time
StartTime = time.time()
cnt = 0
print(sieve_method(25))
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

출력

위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -

2
3
5
7
11
13
17
19
23
Time Elapsed is: 0.0