[Codility] 11. Sieve of Eratosthenes (CountNonDivisible)

11. Sieve of Eratosthenes

에라토스테네스의 체→ N보다 작거나 같은 모든 소수 찾기

1. 2~N 모든 수 나열
2. 제거 되지 않은 가장 작은 수 i의 배수들 모두 제거
3. 2를 계속 반복
4. 남아있는 수가 소수

11.1 CountNonDivisible

For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors. Write a func that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.

 

0 ≤ i < N이 되도록 하는 A[i] 각각에 대하여, 우리는 배열의 A[i]의 나눗셈이 아닌 원소의 개수를 세고자 합니다. 우리는 이 원소들을 '비 나눗셈'이라고 합니다. N개의 정수로 구성된 배열 A가 주어졌을 때, '비 나눗셈'의 양을 나타내는 정수의 수열을 반환하는 함수를 작성하십시오.

 

def solution(A):
   mx = max(A) #A의 최대값
   freq = [0] * (mx+1)
    #갯수세기
   for a in A:
      freq[a] +=1

   div = {} #div[a]에 a의 약수값들 넣을거임
   for a in set(A): #중복없애고 순환
      div[a] = list(set([1, a]))
   i = 2
   while i*i <= mx:
      k = i
      while k <= mx:
         if k in div and not i in div[k]: #div에 key값이 k가 있고, div[k]안에 k의 약수 i가 없는 경우
            div[k] += list(set( [i, k // i] )) # 0들어가도freq[0]에 아무값없어서 상관없어
         k += i
      i += 1
   result = []
   for a in A:
      cnt = 0
      for d in div[a]:
         cnt += freq[d]
      result.append( len(A) - cnt )
   return result