숫자를 1부터 시작해서 하나씩 늘려나가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다. 우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 점입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다. 이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.
10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다. 이백만(2,000,000) 이하 소수의 합은 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=10) 이전에 만든 소수 판별 함수를 사용하면 간단히 풀 수 있는 문제이다. 소수 판별 함수의 성능 자체는 나쁘지 않지만, 루프를 200만번 돌아야 하기 때문에 시간이 제법 오래 걸리는 것은 어쩔 수 없다. 사실 2를 제외한 모든 짝수는 소수가 아니므로, 다음과 같이 홀수만 검사하도록하면 검사 횟수를 절반으로 줄일 수 있다. 이론상으로는 그렇지만 성능상으로는 그다지 향상이 체감되지 않을 것이다. 어차피 짝수들은… 더 보기 »오일러 프로젝트 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]]
