오일러 프로젝트 58

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

오일러 프로젝트 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)))

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

가장 빠른 알고리듬 현재까지 순수 파이썬으로 작성된 알고리듬 중 가장 빠른 것으로 알려진 것은 @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,