Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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);
}
}
}
Owner

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

C++ solution compiled using the following:

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

Owner

Added new JavaScript and CoffeeScript solutions

Owner

Added solution in Go

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