오일러 프로젝트 58 번 문제는 28번 문제와 비슷한 나선모양 격자를 늘려가면서 대각선에 존재하는 숫자중에서 소수의 비율이 10%미만이 될 때의 사각형의 크기(한변의 길이)를 구하는 문제이다. 종료 범위를 미리 알 수 없기 때문에 나선을 따라가며 소수인 수와 소수가 아닌 수를 모두 세어서 그 비율을 계산해야 하기 때문에 소수 판별 검사 함수의 성능이 매우 중요하다.
오일러 프로젝트 58 더보기Tag: Prime number
오일러 프로젝트 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))))
체를 사용하여 소수 집합 구하기
가장 빠른 알고리듬
현재까지 순수 파이썬으로 작성된 알고리듬 중 가장 빠른 것으로 알려진 것은 @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]]