반응형
python 소수 구하는 알고리즘
sieve algorithm
def primes(n):
""" returns a list of prime numbers from 2 to < n """
if n < 2: return []
if n == 2: return [2]
# do only odd numbers starting at 3
s = range(3, n, 2)
# n**0.5 may be slightly faster than math.sqrt(n)
mroot = n ** 0.5
half = len(s)
i = 0
m = 3
while m <= mroot:
if s[i]:
j = (m * m - 3)//2
s[j] = 0
while j < half:
s[j] = 0
j += m
i = i + 1
m = 2 * i + 3
# make exception for 2
return [2]+[x for x in s if x]
print '-' * 50 # print 50 dashes, cosmetic
num = 1000000
primeList = primes(num)
print "List of prime numbers from 2 to < %d:" % num
print primeList
반응형
'IT' 카테고리의 다른 글
| sketcup 습작 입니다. (0) | 2012.11.30 |
|---|---|
| app web 설정 option (0) | 2012.05.29 |
| syslog-ng.conf 파일 (0) | 2012.03.20 |
| 만번 마운트 후에 fsck 로 파일 시스템 check 해라 (0) | 2012.02.29 |
| 키보드 마우스 공유 프로그램 synergy (0) | 2012.01.17 |
