Instantly share code, notes, and snippets.

dazfuller/Challenge1.cs Last active Dec 10, 2015

Gets the first 10,000 prime numbers and calculates the sum of the values which are palindromic
 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"
 #include #include #include #include #include #include #include using namespace std; int getUpperLimit(int value) { auto n = static_cast(value); return static_cast(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(sqrt(static_cast(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 " << 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 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(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; }
 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)) }
 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");
 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))
 // 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); } } }
Owner

dazfuller commented Jan 11, 2013

 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
Owner

dazfuller commented Jan 14, 2013

 C++ solution compiled using the following: g++ -Wall -Werror -O3 --std=c++11 -o c1.exe c1.cpp
Owner

dazfuller commented Jul 30, 2013

 Added new JavaScript and CoffeeScript solutions
Owner