[Euler Project 187] 인자가 두개인 합성수의 갯수

1억보다 작은, 소수 둘만의 곱인 합성수의 갯수를 구하라. 4나 9도 포함된다. 에라스토테네스의 체 방법으로 소수를 우선 싹 구하고 한다. 내가 가장 효율적이라고 생각했던 소수 구하는 방법은 전혀 효율적이지 않았다.

---

#!/usr/bin/env python

# http://projecteuler.net/index.php?section=problems&id=187

MAX=50000000
flags = [ 1 ] * MAX

flags[0] = 0
flags[1] = 0
for n in range(2, MAX):
       if flags[n] == 1:
               m = 2*n
               while m < MAX:
                       flags[m] = 0
                       m+=n
       n+=1
primes = [ ]
for i in range(0, MAX):
       if flags[i] == 1:
               primes.append(i)
count = 0
count += len(primes)
i = 1
while primes[i]*primes[i] < 2*MAX:
       cnt = 0
       max = (2*MAX)//primes[i]
       j = i
       while 1:
               if primes[j] > max:
                       break
               j+=1
               cnt+=1
       count+=cnt
       i+=1
print(count)

---