에라토스테네스의 체 (소수 구하기)

아현·2021년 7월 8일
0

Algorithm

목록 보기
161/400

에라토스테네스의 체


  • 다음의 코드는 해당 수보다 작은 모든 수로 나누어 보아서 소수인지를 판단하는 방법으로, 소수의 정의에 충실한 방법이면서 무식하지만 가장 강력한 방법이다.

    • 한 개의 소수를 구할 때는 그런대로 괜찮은 방법인데 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다.

n=100

def isPrime(a):
  if(a<2):
    return False
  for i in range(2,a):
    if(a%i==0):
      return False
  return True

for i in range(n+1):
  if(isPrime(i)):
    print(i)

  • 소수를 구하기 위해 에라토스테네스가 제안한 방법은 다음과 같다.



방식

  • 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

    1) 1은 제거

    2) 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

    3) 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

    4) 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

    5) (반복)



n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)






약수 구하기


import math

def get_divisor(num):
    divisors = [] #약수
    length = int(math.sqrt(num)) + 1 # 10^2 > 90이므로 11보다 작은 수만큼 나누면 결과를 얻을 수 있다.
    
  for i in range(1, length):
    if num % i == 0:
        divisors.append(i)
        divisiors.append(num // i)
        
   divisors.sort()
   return divisors
   
   
print(get_divisor(90))


      
      


profile
For the sake of someone who studies computer science

0개의 댓글