알고리즘-에라토스테네스의 체

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체

  • 소수를 판별하는 알고리즘이다.
  • 소수들을 대량으로 빠르고 정확하게 구하는 방법
  1. 1 은제거
  2. 지워지지 않는 수 중 제일 작은 2를 소수로 택하고 , 나머지 2의 배수를 모두 지운다.
  3. 지워지지 않는 수 중 제일 작은 3을 소수로 택하고 , 나머지 3의 배수를 모두 지운다.
  4. 지워지지 않는 수 중 제일 작은 5를 소수로 택하고 , 나머지 5의 배수를 모두 지운다.
  5. 반복

def solution(n):
    sum = 0
    s = 0
    for i in range(2, n + 1):
        for j in range(2, i):
            if i % j == 0:
                s += 1
        if s == 0:
            sum += 1
        s = 0

    return sum

좋은 웹페이지 즐겨찾기