오일러 프로젝트 58

오일러 프로젝트 58 번 문제는 28번 문제와 비슷한 나선모양 격자를 늘려가면서 대각선에 존재하는 숫자중에서 소수의 비율이 10%미만이 될 때의 사각형의 크기(한변의 길이)를 구하는 문제이다. 종료 범위를 미리 알 수 없기 때문에 나선을 따라가며 소수인 수와 소수가 아닌 수를 모두 세어서 그 비율을 계산해야 하기 때문에 소수 판별 검사 함수의 성능이 매우 중요하다.

오일러 프로젝트 58 더보기

오일러 프로젝트 46

오일러 프로젝트 46 번은 은근히 시간이 많이 걸리는 문제이다. 모든 소수가 아닌 홀수가 소수와 제곱수의 두 배의 합으로 나타낼 수 있다는 추측의 반례를 찾는 것이다.  오일러 프로젝트 46 더보기

오일러 프로젝트 010

오일러 프로젝트 10번

10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다. 이백만(2,000,000) 이하 소수의 합은 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=10)

지난 번에 만든 isPrime() 함수를 이용해서 다음과 같이 풀면 되는데…

print sum((x for x in range(2000000+1) if isPrime(x)))

오일러 프로젝트 010 더보기

체를 사용하여 소수 집합 구하기

가장 빠른 알고리듬

현재까지 순수 파이썬으로 작성된 알고리듬 중 가장 빠른 것으로 알려진 것은 @Robert William Hanks가 개발한 아래 알고리듬이다.

def primes(n):
    """Return a list of primes under n"""
    sieve = [True] * (n/2)
    for i in xrange(3, int(n**0.5)+1, 2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1, n/2) if sieve[i]]