Subscribe to gabehabe's on-topic ramblings        RSS Feed
-----

Circular Primes

Icon 5 Comments
WARNING : CONTAINS SPOILERS! :)

Decided to blog about some of the more interesting project euler tasks here. Could lead to some interesting discussion on algorithms, too. :w00t:

I won't be blogging about every problem I work on, and I don't spend too much time on there, but it's nice to try your hand at a challenge. :)

The least efficient part of this code is rotate_int which I threw together in about 5 minutes. I'm happy though, since it works and I can solve the problem in ~3.5 seconds using this program. (2.5s of which is used to determine all primes below 1,000,000)
Here's the code for the rotate_int function:
int rotate_int(int x, int rotations) {
    vector<int> vec;
    ostringstream ostr;
    ostr << x;
    string str = ostr.str();
    for(unsigned int i = 0; i < str.length(); i++) {
        vec.push_back(str[i]-48);
    }
    rotate(vec.begin(), vec.begin()+rotations, vec.end());
    int mul = 1;
    for(unsigned int i = 1; i < vec.size(); i++) {
        mul *= 10;
    }
    x = 0;
    for(unsigned int i = 0; i < vec.size(); i++) {
        x += vec[i] * mul;
        mul /= 10;
    }
    return x;
}
Told you it was inefficient! :P

The rest of the program is really just a wrapper for that prime bitset.

The final product is this:
/* WARNING - CONTAINS SPOILERS!
 * Project Euler - Problem 35
 * Circular primes
 * [url="http://projecteuler.net/index.php?section=problems&id=35"]http://projecteuler.net/index.php?section=problems&id=35[/url]
 * Author: Danny Battison
 */
#include <iostream>
#include <bitset>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 1000000;

void output(bitset<MAX> primes) {
    for(int i = 0; i < MAX; i++) {
        if(primes[i] == 1) {
            cout << i << " ";
        }
    }
}

int get_nth_prime(int n, bitset<MAX> primes) {
    int count = 0;
    for(int i = 2; i < MAX; i++) {
        if(primes[i]) {
            count++;
        } if(count == n) {
            return i;
        }
    }
    return 0; // could not find
}

int rotate_int(int x, int rotations) {
    vector<int> vec;
    ostringstream ostr;
    ostr << x;
    string str = ostr.str();
    for(unsigned int i = 0; i < str.length(); i++) {
        vec.push_back(str[i]-48);
    }
    rotate(vec.begin(), vec.begin()+rotations, vec.end());
    int mul = 1;
    for(unsigned int i = 1; i < vec.size(); i++) {
        mul *= 10;
    }
    x = 0;
    for(unsigned int i = 0; i < vec.size(); i++) {
        x += vec[i] * mul;
        mul /= 10;
    }
    return x;
}

int main() {
    bitset <MAX> primes;
    for(int i = 2; i < MAX; i++) {
        primes[i] = 1;
    }
    // quick sieve of eratosthenes -- start it off
    int sieve[] = {2,3,5,7}; // give it a few primes to start with
    for(int mul = 0; mul < 4; mul++) {
        for(int i = 1; i < MAX; i++) {
            if(i % sieve[mul] == 0 && i != sieve[mul]) {
                primes[i] = 0;
            }
        }
    }

    // by now, we have a list of primes with some larger numbers still left
    // in order to remove those, we now need to run through primes and
    // make sure to remove multiples of primes up to sqrt(MAX)
    for(int i = 2; i < sqrt(MAX); i++) {
        if(primes[i]) {
            for(int j = i+1; j < MAX; j++) {
                if(j % i == 0) {
                    primes[j] = 0;
                }
            }
        }
    }

    // this section takes approx 1s - could be reduced GREATLY
    // but I'm lazy.
    ostringstream ostr;
    int len;
    bool t = 0;
    int count = 0;
    int x;
    for(int i = 1; i < MAX; i++) {
        if(primes[i]) {
            ostr.str("");
            ostr << i;
            len = ostr.str().length();
            for(int j = 0; j < len; j++) {
                x = rotate_int(i, j);
                t = primes[x];
                if(!t) break;
            }
            if(t) {
                count++;
            }
        }
    }cout << count;

    return 0;
}

5 Comments On This Entry

Page 1 of 1

gabehabe Icon

12 June 2009 - 10:02 AM
Here's another one. I forgot which number it was but this was a pretty fun little challenge. Truncatable primes: It takes a while to get the last one, but the first 10 are really fast. Open to suggestions on how that last one could be improved.
/* WARNING - CONTAINS SPOILERS!
 * Project Euler - Problem 35
 * Circular primes
 * [url="http://projecteuler.net/index.php?section=problems&id=35"]http://projecteuler.net/index.php?section=problems&id=35[/url]
 * Author: Danny Battison
 */
#include <iostream>
#include <bitset>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 1000000;

void output(bitset<MAX> primes) {
    for(int i = 0; i < MAX; i++) {
        if(primes[i] == 1) {
            cout << i << " ";
        }
    }
}

int get_nth_prime(int n, bitset<MAX> primes) {
    int count = 0;
    for(int i = 2; i < MAX; i++) {
        if(primes[i]) {
            count++;
        } if(count == n) {
            return i;
        }
    }
    return 0; // could not find
}

bool is_truncatable_rtl(int prime, bitset<MAX>primes) {
    if(prime < 10 || !primes[prime]) return false; // only 1 digit, not considered truncatable
    while(prime > 0) {
        if(primes[prime]) {
            prime /= 10;
        } else {
            return false;
        }
    } return true;
}

int string_to_int(string str) {
    int mul = 1;
    for(unsigned int i = 1; i < str.length(); i++) {
        mul *= 10;
    }

    int x = 0;
    for(unsigned int i = 0; i < str.length(); i++) {
        x += (str[i] - 48) * mul;
        mul /= 10;
    }
    return x;
}

bool is_truncatable_ltr(int prime, bitset<MAX>primes) {
    if(prime < 10 || !primes[prime]) return false;
    ostringstream ostr;
    ostr << prime;
    string str = ostr.str();
    unsigned int len = str.length();
    for(unsigned int i = 0; i < len-1; i++) {
        str = str.replace(0,1, "");
        if(!primes[string_to_int(str)]) {
            return false;
        }
    } return true;
}

int main() {
    bitset <MAX> primes;
    for(int i = 2; i < MAX; i++) {
        primes[i] = 1;
    }
    // quick sieve of eratosthenes -- start it off
    int sieve[] = {2,3,5,7}; // give it a few primes to start with
    for(int mul = 0; mul < 4; mul++) {
        for(int i = 1; i < MAX; i++) {
            if(i % sieve[mul] == 0 && i != sieve[mul]) {
                primes[i] = 0;
            }
        }
    }

    // by now, we have a list of primes with some larger numbers still left
    // in order to remove those, we now need to run through primes and
    // make sure to remove multiples of primes up to sqrt(MAX)
    for(int i = 2; i < sqrt(MAX); i++) {
        if(primes[i]) {
            for(int j = i+1; j < MAX; j++) {
                if(j % i == 0) {
                    primes[j] = 0;
                }
            }
        }
    }

    int sum = 0;
    int count = 0;
    for(int i = 0; i < MAX; i++) {
        if(is_truncatable_rtl(i, primes) && is_truncatable_ltr(i, primes)) {
            count++;
            sum += i;
            cout << i << endl;
            if(count == 11) break; // there are only 11
        }
    }
    cout << sum;

    return 0;
}
0

AdamSpeight2008 Icon

12 June 2009 - 05:18 PM
It must be a bad implementation as I can write one in vb.net that takes ~255ms (thats includes find the primes and printing out.)
0

gabehabe Icon

12 June 2009 - 05:19 PM
Yeah, but you're a genius. :P

Care to share?
0

AdamSpeight2008 Icon

12 June 2009 - 09:23 PM
Made a slight mistake used 100000 instead of 1000000, so altered the algorithm used a million algorithm and i get ~802ms. (Using the parallel extensions in vs2010 i get ~620 with 2 Cores)
Module Module1
 Dim DC As New HashSet(Of Char)
 Sub Main()
  DC.Add("2")
  DC.Add("4")
  DC.Add("6")
  DC.Add("8")
  DC.Add("0")
  DC.Add("5")

  Dim max As Integer = 1000000
  Dim sw As New Diagnostics.Stopwatch
  sw.Start()

  Dim Primes() As Integer = (From X As Integer In Enumerable.Range(2, max - 1) Where IsPrime(X) AndAlso ND(X.ToString) Select X).ToArray

  Console.WriteLine("Primes: {0} in {1}", Primes.Count, sw.Elapsed)
  Dim CircularPrimes = (From x As Integer In Primes Select x Where AllRotationPrime(Primes, x))
  Console.WriteLine("Circular Primes: {0} in {1}", CircularPrimes.Count, sw.Elapsed)
  For i As Integer = 0 To CircularPrimes.Count - 1
   Console.WriteLine("{0}:= {1}", i + 1, CircularPrimes(i))
  Next
  sw.Stop()
  Console.WriteLine("Printed Circular Primes: {0} in {1}", CircularPrimes.Count, sw.Elapsed)
  Console.ReadLine()
 End Sub
 Private Function IsPrime(ByRef x As Integer) As Boolean
  If x <= 0 Then Return False
  If x = 2 Then Return True
  If x = 3 Then Return True
  If x = 5 Then Return True
  If x Mod 2 = 0 Then Return False
  If x < 4 Then Return True
  Dim sqr As Integer = Math.Round(Math.Sqrt(x), 0, MidpointRounding.AwayFromZero)
  If sqr Mod 2 = 0 Then sqr += 1
  Dim i As Integer = 1
  While i <= sqr
   i += 2
   If x Mod i = 0 Then Return False
  End While
  Return True
 End Function
 Private Function ND(ByRef N As String) As Boolean
  If N = "2" Then Return True
  If N = "3" Then Return True
  If N = "5" Then Return True
  For Each NC As Char In N
   If DC.Contains(NC) Then Return False
  Next
  Return True

 End Function

 Private Function AllRotationPrime(ByRef p As IEnumerable(Of Integer), ByVal n As String) As Boolean
  For i As Integer = 0 To n.Length - 2
   n = n.Substring(1) & n(0)
   If p.Contains(n) = False Then Return False
  Next
  Return True
 End Function

End Module



vs2010 Version
Module Module2
  Dim DC As New HashSet(Of Char)
  Sub Main()
	DC.Add("2")
	DC.Add("4")
	DC.Add("6")
	DC.Add("8")
	DC.Add("0")
	DC.Add("5")

	Dim max As Integer = 1000000
	Dim sw As New Diagnostics.Stopwatch
	sw.Start()

	Dim Primes() As Integer = (From X As Integer In ParallelEnumerable.Range(2, max - 1) Where IsPrime(X) AndAlso ND(X.ToString) Select X).ToArray

	Console.WriteLine("Primes: {0} in {1}", Primes.Count, sw.Elapsed)
	Dim CircularPrimes = (From x As Integer In Primes.AsParallel Select x Where AllRotationPrime(Primes, x))
	Console.WriteLine("Circular Primes: {0} in {1}", CircularPrimes.Count, sw.Elapsed)
	For i As Integer = 0 To CircularPrimes.Count - 1
	  Console.WriteLine("{0}:= {1}", i + 1, CircularPrimes(i))
	Next
	sw.Stop()
	Console.WriteLine("Printed Circular Primes: {0} in {1}", CircularPrimes.Count, sw.Elapsed)
	Console.ReadLine()
  End Sub
  Private Function IsPrime(ByRef x As Integer) As Boolean
	If x <= 0 Then Return False
	If x = 2 Then Return True
	If x = 3 Then Return True
	If x = 5 Then Return True


	If x Mod 2 = 0 Then Return False
	If x < 4 Then Return True
	Dim sqr As Integer = Math.Round(Math.Sqrt(x), 0, MidpointRounding.AwayFromZero)
	If sqr Mod 2 = 0 Then sqr += 1
	Dim i As Integer = 1
	While i <= sqr
	  i += 2
	  If x Mod i = 0 Then Return False
	End While
	Return True
  End Function
  Private Function ND(ByRef N As String) As Boolean
	If N = "2" Then Return True
	If N = "3" Then Return True
	If N = "5" Then Return True
	For Each NC As Char In N
	  If DC.Contains(NC) Then Return False
	Next
	Return True

  End Function



  Private Function AllRotationPrime(ByRef p As IEnumerable(Of Integer), ByVal n As String) As Boolean
	For i As Integer = 0 To n.Length - 2
	  n = n.Substring(1) & n(0)
	  If p.Contains(n) = False Then Return False
	Next
	Return True
  End Function
  Private Function CheckForRotationInList(ByRef p As IEnumerable(Of Integer), ByVal n As String) As Boolean
	For i As Integer = 0 To n.Length - 2
	  n = n.Substring(1) & n(0)
	  If p.Contains(n) Then Return False
	Next
	Return True
  End Function

End Module



If somebody with more cores try it out?
0

RetardedGenius Icon

18 May 2011 - 02:29 PM
I wrote this solution a while ago in C# (I mainly use C++ now.) I'm no genius, however it executes in less time that yours, when using my i3 M 350 @2.27 GHz.

Spoiler

I think it is because of the method you are using to test numbers for primality mate. I would always suggest using a sieve for a problem like this, as they are much faster. However you could improve your algorithm significantly by observing that all primes, except 2 and 3, are of the form 6n 1. :)

PS: As coincidence would have it I started a topic about Project Euler yesterday, here.
0
Page 1 of 1

July 2014

S M T W T F S
  12345
6789101112
13141516171819
202122 23 242526
2728293031  

Request A Topic!

Want me to blog about something? Perhaps a language? A piece of software? A specific topic? Let me know! Even guests can post here on my blog!

If you would like to request a topic, please post a comment here and I'll get on it right away! smile.gif

Search My Blog

1 user(s) viewing

1 Guests
0 member(s)
0 anonymous member(s)

gabehabe's off-topic ramblings

Follow me on Twitter!
lol, my other blog died a horrible lonely death. Ah well.

Smiley of the [however often I change it]

IPB Image

Contact Me

e-mail: gabehabe@gmail.com

Google Talk: gabehabe@gmail.com
MSN: gabehabe@hotmail.com
Yahoo: gabehabe (rarely used)
AIM: gabehabe (rarely used)

Skype: gabehabe

Want me to work for you? [click]