Last active
December 10, 2015 23:08
-
-
Save dazfuller/4507549 to your computer and use it in GitHub Desktop.
Gets the first 10,000 prime numbers and calculates the sum of the values which are palindromic
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
getUpperLimit = (n) -> | |
Math.floor(n * Math.log(n) * 1.138) | |
isPalindrome = (n) -> | |
str = String n | |
str2 = str.split('').reverse().join('') | |
str is str2 | |
getPrimes = (n) -> | |
upper = getUpperLimit(n) | |
sieve_length = upper + 1 | |
sieve = ((if i % 2 is 0 then false else true) for i in [0..sieve_length]) | |
sieve_end = Math.sqrt upper | |
sieve[0] = sieve[1] = false | |
sieve[2] = true | |
i = 3 | |
while i < sieve_end | |
if sieve[i] is true | |
j = i * 2 | |
while j < sieve_length | |
sieve[j] = false | |
j += i | |
i += 2 | |
return (index for value, index in sieve when value is true).slice(0, n) | |
t0 = Date.now() | |
primes = getPrimes(10000) | |
sumOfPalindromes = (x for x in primes when isPalindrome(x) is true).reduce (a, b) -> a + b | |
t1 = Date.now() | |
console.log "The sum of the palindromic primes is: #{sumOfPalindromes}" | |
console.log "The largest prime number returned was: #{primes[primes.length-1]}" | |
console.log "The solution to #{t1-t0}ms to run" |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <chrono> | |
#include <cmath> | |
#include <stdexcept> | |
#include <iostream> | |
#include <string> | |
#include <time.h> | |
using namespace std; | |
int getUpperLimit(int value) | |
{ | |
auto n = static_cast<double>(value); | |
return static_cast<int>(n * log(n) * 1.26); | |
} | |
int* getPrimeNumbers(int limit) | |
{ | |
auto upper_limit = getUpperLimit(limit) + 1; | |
auto sieve_length = upper_limit + 1; | |
bool* sieve = new bool[sieve_length]; | |
// Initialize the array, cannot guarantee that the values held are true or false | |
fill_n(sieve, sieve_length, true); | |
sieve[0] = sieve[1] = false; | |
sieve[2] = true; | |
auto upper = static_cast<int>(sqrt(static_cast<double>(upper_limit))); | |
for (auto i = 3; i <= upper; i += 2) | |
{ | |
if (sieve[i] == true) | |
{ | |
for (auto j = i * 2; j < sieve_length; j += i) | |
{ | |
sieve[j] = false; | |
} | |
} | |
} | |
auto primes = new int[limit]; | |
primes[0] = 2; | |
auto count = 1; | |
for (auto i = 3; i < sieve_length && count < limit; i += 2) | |
{ | |
if (sieve[i] == true) | |
{ | |
primes[count++] = i; | |
} | |
} | |
delete[] sieve; | |
return primes; | |
} | |
bool isPalindrome(int value) | |
{ | |
string str = to_string(value); | |
auto cx = str.length(); | |
if (cx == 1) | |
{ | |
return true; | |
} | |
unsigned int i = 0; | |
unsigned int j = cx - 1; | |
unsigned int end = cx / 2; | |
for (; i < end; i++, j--) | |
{ | |
if (str[i] != str[j]) | |
{ | |
return false; | |
} | |
} | |
return true; | |
} | |
double diffClock(clock_t t0, clock_t t1) | |
{ | |
double diffTicks = t1 - t0; | |
return (diffTicks * 1000) / CLOCKS_PER_SEC; | |
} | |
int main(int argc, char** argv) | |
{ | |
if (argc < 2) | |
{ | |
cout << "example usage: c1 <prime count>" << endl; | |
return -1; | |
} | |
int count = 0; | |
try | |
{ | |
count = stoi(argv[1]); | |
} | |
catch (logic_error&) | |
{ | |
cout << "Error: Unable to convert value '" << argv[1] << "' to an integer" << endl; | |
return -1; | |
} | |
std::chrono::time_point<std::chrono::high_resolution_clock> start, end; | |
start = chrono::high_resolution_clock::now(); | |
auto prime_count = count; | |
auto primes = getPrimeNumbers(prime_count); | |
auto sum_of_primes = 0; | |
auto prime = 0; | |
for (auto i = 0; i < prime_count; i++) | |
{ | |
prime = primes[i]; | |
if (isPalindrome(prime) == true) | |
{ | |
sum_of_primes += prime; | |
} | |
} | |
end = std::chrono::high_resolution_clock::now(); | |
int elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); | |
cout << "The sum of the palindromic primes is: " << sum_of_primes << endl; | |
cout << "The largest prime number returned was: " << primes[prime_count - 1] << endl; | |
cout << "The solution took " << elapsed_time << "ms to run" << endl; | |
delete[] primes; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
"math" | |
"strconv" | |
"time" | |
) | |
type Prime struct { | |
Number int64 | |
IsPalindrome bool | |
} | |
func getUpperLimit(nthPrime int64) int64 { | |
n := float64(nthPrime) | |
x := n * math.Log(n) * 1.35 | |
return int64(x) | |
} | |
func getPrimesNumbers(n int64) ([]Prime, int64) { | |
end := getUpperLimit(n) | |
ar := make([]bool, end) | |
primes := make([]Prime, n) | |
primes[0] = Prime{2, true} | |
primeCount := int64(1) | |
limit := int64(math.Sqrt(float64(end))) + int64(1) | |
for i := int64(3); i < limit; i += 2 { | |
if ar[i] == false { | |
primes[primeCount] = Prime{i, isPalindrome(i)} | |
primeCount += 1 | |
for j := i * 2; j < end; j += i { | |
ar[j] = true | |
} | |
} | |
} | |
sumOfPalindromes := int64(0) | |
for i := limit; i < end && primeCount < n; i += 2 { | |
if ar[i] == false { | |
palindromic := isPalindrome(i) | |
primes[primeCount] = Prime{i, palindromic} | |
if palindromic { | |
sumOfPalindromes += i | |
} | |
primeCount += 1 | |
} | |
} | |
return primes, sumOfPalindromes | |
} | |
func isPalindrome(value int64) bool { | |
str := strconv.FormatInt(value, 10) | |
strlen := len(str) | |
end := strlen / 2 | |
for i, j := 0, strlen-1; i < end; i, j = i+1, j-1 { | |
if str[i] != str[j] { | |
return false | |
} | |
} | |
return true | |
} | |
func main() { | |
t0 := time.Now() | |
ps, sumOfPalindromes := getPrimesNumbers(10000) | |
t1 := time.Now() | |
fmt.Printf("The sum of the palindromic primes is: %d\n", sumOfPalindromes) | |
fmt.Printf("The largest prime number returned was: %d\n", ps[len(ps)-1].Number) | |
fmt.Printf("The solution took %v to run\n", t1.Sub(t0)) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var challenge; | |
(function () { | |
"use strict"; | |
function getUpperLimit(n) { | |
return Math.floor(n * Math.log(n) * 1.138); | |
} | |
function getNPrimes(limit) { | |
var upper = getUpperLimit(limit), | |
sieve_length = upper + 1, | |
sieve = [], | |
sieve_end = Math.sqrt(upper), | |
primes = new Uint32Array(limit), | |
count = 1, | |
i = 0, | |
j = 0; | |
sieve[0] = sieve[1] = false; | |
sieve[2] = true; | |
primes[0] = 2; | |
for (i = 3; i < sieve_length; i += 1) { | |
sieve[i] = true; | |
} | |
for (i = 3; i < sieve_end; i += 2) { | |
if (sieve[i] === true) { | |
sieve[i] = true; | |
for (j = i * 2; j < sieve_length; j += i) { | |
sieve[j] = false; | |
} | |
} | |
} | |
for (i = 3; i < sieve_length && count < limit; i += 2) { | |
if (sieve[i] === true) { | |
primes[count] = i; | |
count += 1; | |
} | |
} | |
return primes; | |
} | |
function isPalindrome(value) { | |
var str = String(value), | |
i = 0, | |
j = str.length - 1, | |
end = str.length / 2; | |
for (i = 0; i < end; i += 1, j -= 1) { | |
if (str[i] !== str[j]) { | |
return false; | |
} | |
} | |
return true; | |
} | |
challenge = { | |
GetNPrimes: getNPrimes, | |
IsPalindrome: isPalindrome | |
}; | |
}()); | |
var t0 = Date.now(), | |
t1 = t0, | |
primes = challenge.GetNPrimes(10000), | |
sum = 0, | |
prime = 0, | |
i = 0, | |
j = 0; | |
for (i = 0, j = primes.length; i < j; i += 1) { | |
prime = primes[i]; | |
if (challenge.IsPalindrome(prime)) { | |
sum += prime; | |
} | |
} | |
t1 = Date.now(); | |
console.log("The sum of the palindromic primes is: " + sum); | |
console.log("The largest prime number returned was: " + primes[primes.length - 1]); | |
console.log("The solution took " + (t1 - t0) + "ms to run\n"); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from math import floor, log, sqrt | |
from time import time | |
class Challenge: | |
def get_upper_limit(self, n): | |
return floor(n * log(n) * 1.138) | |
def get_n_primes(self, limit): | |
upper_limit = self.get_upper_limit(limit) | |
sieve_length = upper_limit + 1 | |
sieve = [False, False, True] | |
sieve += [True, False] * floor(((sieve_length - 2) / 2)) | |
sieve[0] = sieve[1] = False | |
upper = floor(sqrt(upper_limit)) + 1 | |
for i in range(3, upper, 2): | |
if sieve[i] is True: | |
for j in range(i * 2, sieve_length, i): | |
sieve[j] = False | |
return [i for i, v in enumerate(sieve) if v is True][:limit] | |
def is_palindrome(self, value): | |
n = str(value) | |
return n == n[::-1] | |
if __name__ == "__main__": | |
c = Challenge() | |
t0 = time() | |
primes = c.get_n_primes(10000) | |
sum_of_palindromes = sum([p for p in primes if c.is_palindrome(p) is True]) | |
t1 = time() | |
print("The sum of the palindromic primes is:", sum_of_palindromes) | |
print("The largest prime number returned was:", primes[-1]) | |
print("The solution took %.3fms to run" % ((t1 - t0) * 1000)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// From the first 10,000 prime numbers, calculate the sum of the palindromic primes | |
[assembly: System.CLSCompliant(true)] | |
[assembly: System.Runtime.InteropServices.ComVisible(false)] | |
[assembly: System.Reflection.AssemblyVersion("1.0.0.0")] | |
[assembly: System.Reflection.AssemblyProduct("Performance Challenge - 1")] | |
namespace Challenge | |
{ | |
using System; | |
using System.Collections; | |
using System.Globalization; | |
public static class Primes | |
{ | |
private static int GetUpperLimit(int value) | |
{ | |
var x = Convert.ToDouble(value); | |
return Convert.ToInt32(x * Math.Log(x) * 1.26); | |
} | |
public static int[] GetPrimeNumbers(int limit) | |
{ | |
var upperLimit = GetUpperLimit(limit) + 1; | |
var sieve = new BitArray(upperLimit, true); | |
sieve[0] = sieve[1] = false; | |
sieve[2] = true; | |
var upper = Convert.ToInt32(Math.Sqrt(Convert.ToDouble(upperLimit))); | |
for (var i = 3; i <= upper; i += 2) | |
{ | |
if (sieve[i] == true) | |
{ | |
for (var j = i * 2; j < sieve.Length; j += i) | |
{ | |
sieve[j] = false; | |
} | |
} | |
} | |
var primes = new int[limit]; | |
primes[0] = 2; | |
var count = 1; | |
for (var i = 3; i < sieve.Length && count < limit; i += 2) | |
{ | |
if (sieve[i] == true) | |
{ | |
primes[count] = i; | |
count++; | |
} | |
} | |
return primes; | |
} | |
public static bool IsPalindrome(int value) | |
{ | |
var a = Convert.ToString(value, CultureInfo.InvariantCulture); | |
if (a.Length == 1) | |
{ | |
return true; | |
} | |
var i = 0; | |
var j = a.Length - 1; | |
var end = a.Length / 2; | |
for (; i < end; i++, j--) | |
{ | |
if (a[i] != a[j]) | |
{ | |
return false; | |
} | |
} | |
return true; | |
} | |
} | |
public static class Solution | |
{ | |
public static void Main() | |
{ | |
var t0 = DateTime.Now; | |
var primes = Primes.GetPrimeNumbers(10000); | |
var sumOfPalindromePrimes = 0; | |
foreach (var val in primes) | |
{ | |
if (Primes.IsPalindrome(val)) | |
{ | |
sumOfPalindromePrimes += val; | |
} | |
} | |
var largestPrimeNumber = primes[primes.Length - 1]; | |
var t1 = DateTime.Now; | |
Console.WriteLine("The sum of the palindromic primes is: {0}", sumOfPalindromePrimes); | |
Console.WriteLine("The largest prime number returned was: {0}", largestPrimeNumber); | |
Console.WriteLine("The solution took {0}ms to run", t1.Subtract(t0).Milliseconds); | |
} | |
} | |
} |
C++ solution compiled using the following:
g++ -Wall -Werror -O3 --std=c++11 -o c1.exe c1.cpp
Added new JavaScript and CoffeeScript solutions
Added solution in Go
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is how I'm currently compiling this code on my Windows environment (note, I used the sn.exe tool to create the keyfile being used here)
csc /debug- /optimize+ /w:4 /keyfile:challenge.snk /out:Challenge1.exe Challenge1.cs