Problem 10
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
C#
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Euler { class Program { static void Main(string[] args) { const long pmax = 2000000; bool[] isPrime = new bool[pmax]; for (long i = 2; i < pmax; i++) { isPrime[i] = true; } { const long i = 2; for (long j = 2 * i; j < pmax; j += i) { isPrime[j] = false; } } for (int i = 3; i * i<= pmax; i += 2) { if (!isPrime[i]) continue; for (long j = 2 * i; j < pmax; j += i) { isPrime[j] = false; } } long sum = 0; for (int i = 2; i < pmax; i++) { if (isPrime[i]) sum += i; } Console.WriteLine(sum); } } }
Perl
sub primesUnder {
my ($limit) = @_;
my @p = 0 x $limit;
if ( $limit >= 3 ) { $p[2] = 1; }
for ( my $i = 3 ; $i < $limit ; $i += 2 ) { $p[$i] = 1; }
for ( my $i = 3 ; $i * $i < $limit ; $i += 2 ) {
if ( !$p[$i] ) { next; }
for ( my $j = $i * 2 ; $j < $limit ; $j += $i ) {
$p[$j] = 0;
}
}
my @r = ();
for my $i ( 2 .. $limit - 1 ) {
if ( $p[$i] ) { push( @r, $i ); }
}
return @r;
}
sub problem10 {
print sum( primesUnder(2000000) );
}
problem10();
Python
import mathdef primesUnder(limit):
p = [0] * limit
if limit >= 3: p[2] = True
for i in range(3, limit, 2): p[i] = True
for i in range(3, int(math.sqrt(limit)), 2):
if not p[i]: continue
for j in range(i * 2, limit, i):
p[j] = False
r = []
for i in range(2, limit, 1):
if p[i]: r.append(i)
return r
def problem10():
print(sum(primesUnder(2000000)))
problem10()
Go
func primesUnder(limit int) []int {
p := make([]bool, limit)
if limit >= 3 {
p[2] = true
}
for i := 3; i < limit; i += 2 {
p[i] = true
}
for i := 3; i*i < limit; i += 2 {
if !p[i] {
continue
}
for j := i * 2; j < limit; j += i {
p[j] = false
}
}
r := []int{}
for i := 2; i < limit; i++ {
if p[i] {
r = append(r, i)
}
}
return r
}
func problem10() {
var sum int64 = 0
for _, i := range primesUnder(2000000) {
sum += int64(i)
}
fmt.Println(sum)
}
func main() {
problem10()
}
C++
vector<int> primesUnder(int limit) {
vector<bool> p(limit);
if (limit >= 3) {
p[2] = true;
}
for (auto i = 3; i < limit; i += 2) {
p[i] = true;
}
for (auto i = 3; i*i < limit; i += 2) {
if (!p[i]) {
continue;
}
for (auto j = i * 2; j < limit; j += i) {
p[j] = false;
}
}
vector<int> r;
for (auto i = 2; i < limit; i++) {
if (p[i]) {
r.push_back(i);
}
}
return r;
}
void problem10() {
long long sum = 0;
auto primes = primesUnder(2000000);
for (auto itr = primes.begin(); itr != primes.end(); itr++) {
sum += *itr;
}
cout << sum;
}
Bash (really slow)
function primesUnder {
local limit=$1
if ((limit >= 3)); then
p[2]=1
fi
local i
local j
for ((i=3; i < limit; i += 2)); do
p[i]=1
done
for ((i=3; i*i < limit; i+= 2)); do
if ((!p[i])); then
continue
fi
for ((j=i*2; j<limit; j+=i)); do
p[j]=0
done
done
for ((i=2; i<limit; i++)); do
if ((p[i])); then
echo -n " $i"
fi
done
echo
}
function problem10 {
local sum=0
local primes=$(primesUnder 2000000)
echo $primes
for x in $primes; do
((sum += x))
done
echo $sum
}
function problem10b {
local sum=0
local x
for x in {2..2000000}; do
if isPrime $x; then ((sum+=x)); fi
done
echo $sum
}
problem10b
Javascript
function primesUnder(limit) {
var p = new Array(limit);
if (limit >= 3) p[2] = true;
for (var i = 3; i < limit; i += 2)
p[i] = true;
for (var i = 3; i*i < limit; i += 2) {
if (!p[i]) continue;
for (var j = i * 2; j < limit; j += i)
p[j] = false;
}
var r = [];
for (var i = 2; i < limit; i++)
if (p[i]) r.push(i);
return r;
}
function problem10() {
var sum = 0;
var primes = primesUnder(2000000);
for (var i=0; i<primes.length; i++) sum += primes[i];
return sum;
}
problem10()
Racket
#lang racket
(define (prime? n)
(let loop ([i 2])
(if (<= (* i i) n)
(if (= 0 (modulo n i)) #f
(loop (add1 i)))
#t)))
(define (problem10)
(define sum 0)
(for ([i (in-range 2 2000000)])
(when (prime? i) (set! sum (+ sum i))))
(displayln sum))
(define (primesUnder limit)
(define p (make-vector limit #t))
(let loop ([i 2])
(when (< (* i i) limit)
(when (vector-ref p i)
(for ([j (in-range (* i i) limit i)]) (vector-set! p j #f)))
(loop (+ 1 i))))
(define r (list))
(for ([i (in-range 2 limit)])
(when (vector-ref p i) (set! r (cons i r))))
r)
(define (sumPrimesUnder limit)
(define p (make-vector limit #t))
(for ([i (in-range 2 (sqrt limit))])
(when (vector-ref p i)
(for ([j (in-range (* i i) limit i)]) (vector-set! p j #f))))
(for/sum ([i (in-range 2 limit)]
#:when (vector-ref p i))
i))
(define (problem10a)
(displayln (foldl + 0 (primesUnder 2000000))))
(define (problem10b)
(displayln (sumPrimesUnder 2000000)))
(time (problem10))
(time (problem10a))
(time (problem10b))
* Clojure
(set! *warn-on-reflection* true)
(defn prime? [n]
(loop [i 2]
(if (<= (* i i) n)
(if (zero? (mod n i))
false
(recur (inc i)))
true)))
(defn problem10 []
(println (apply + (filter prime? (range 2 2000000)))))
(defn primesUnder [limit]
(let [p (transient (apply vector (repeat limit true)))]
(doseq [i (range 2 (Math/sqrt limit))]
(when (p i)
(doseq [j (range (* 2 i) limit i)] (assoc! p j false))))
(filter #(p %) (range 2 limit))))
(defmacro loopwhile [init-symbol init whilep step & body]
`(loop [~init-symbol ~init]
(when ~whilep ~@body (recur (+ ~init-symbol ~step)))))
(defn primesUnderb [limit]
(let [p (boolean-array limit true)]
(loopwhile i 2 (< i (Math/sqrt limit)) 1
(when (aget p i)
(loopwhile j (* i 2) (< j limit) i (aset p j false))))
(filter #(aget p %) (range 2 limit))))
(defn sum-primes-under [limit]
(let [p (boolean-array limit true)]
(loopwhile i 2 (< i (Math/sqrt limit)) 1
(when (aget p i)
(loopwhile j (* i 2) (< j limit) i (aset p j false))))
(loop [i 2, sum 0]
(if (< i limit)
(recur (inc i) (if (aget p i) (+ sum i) sum))
sum))))
(defn problem10a []
(println (apply + (primesUnder 2000000))))
(defn problem10b []
(println (apply + (primesUnderb 2000000))))
(defn problem10c []
(println (sum-primes-under 2000000)))
;(time (problem10))
;(time (problem10a))
;(time (problem10b))
(time (problem10c))
* newLISP
(define (sum-primes-under limit)
(let (p (array limit '(true)))
(for (i 2 (- (sqrt limit) 1))
(when (p i)
(for (j (* i 2) (- limit 1) i) (setf (p j) false))))
(let (sum 0)
(for (i 2 (- limit 1))
(when (p i) (setq sum (+ sum i))))
sum)))
(define (problem10c)
(println (sum-primes-under 2000000)))
(time (problem10c))
'Project Euler' 카테고리의 다른 글
Project Euler Problem 12 (0) | 2012.05.29 |
---|---|
Project Euler Problem 11 (0) | 2012.05.29 |
Project Euler Problem 9 (0) | 2012.05.28 |
Project Euler Problem 8 (0) | 2012.05.28 |
Project Euler Problem 7 (0) | 2012.05.28 |