Skip to content

Instantly share code, notes, and snippets.

@dazfuller
Last active December 10, 2015 23:08
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
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
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 <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;
}
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);
}
}
}
@dazfuller
Copy link
Author

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

@dazfuller
Copy link
Author

C++ solution compiled using the following:

g++ -Wall -Werror -O3 --std=c++11 -o c1.exe c1.cpp

@dazfuller
Copy link
Author

Added new JavaScript and CoffeeScript solutions

@dazfuller
Copy link
Author

Added solution in Go

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment