Dream.In.Code -> Circular Primes

Subscribe to gabehabe's on-topic ramblings

Circular Primes

12 June 2009

5 Comments

Tags: Project Euler

Posted by gabehabe

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!

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;
}

Share This Entry:

Back to gabehabe's on-topic ramblings →

5 Comments On This Entry

Page 1 of 1

gabehabe

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;
}

AdamSpeight2008

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.)

gabehabe

12 June 2009 - 05:19 PM

Yeah, but you're a genius.

Care to share?

AdamSpeight2008

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?

RetardedGenius

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

using System;
using System.Collections;
using System.Linq;
using System.Text;

namespace Problem_35
{
    class Program
    {
        static void Main(string[] args)
        {
            // Generate all of the primes below one million.
            BitArray primeFlags = new BitArray(GeneratePrimes(1000000));

            int prime, max, count = 0;
            string originalPrime, rotation;
            bool isCircular = false;

            for (int i = 2; i < primeFlags.Length; i++)
            {
                if (primeFlags[i]) // The number is prime.
                {
                    prime = i;
                    originalPrime = prime.ToString();
                    rotation = originalPrime;
                    max = rotation.Length - 1;
                    isCircular = true;

                    do
                    {
                        rotation = rotation[max] + rotation.Substring(0, max);

                        if (!primeFlags[Convert.ToInt32(rotation)]) // If the rotation is not a prime number.
                            isCircular = false;

                    } while (rotation != originalPrime); // While the original prime has not been fully rotated.

                    if (isCircular)                      // If all rotations of the prime are also primes.
                        count++;                        // Add one to the number of circular primes found thus far.                   
                }
            }
            Console.WriteLine("Answer = {0}", count);
            Console.ReadKey();
        }
        static BitArray GeneratePrimes(int n)
        {
            BitArray flags = new BitArray(n + 1, true);

            int p = 2;  // 2 is the first known prime, so we'll start here
            bool finished = false;

            flags[0] = false;   // We know that 0 and 1 are not prime
            flags[1] = false;   // so we'd better eliminate them! 

            while (!finished)
            {
                for (int i = p * p; i <= n; i += p)
                    flags[i] = false; // Flag the number as != prime

                if (p * p > n)
                    finished = true;
                else
                    // Identify the next prime
                    for (int j = p + 1; j < n; j++)
                        if (flags[j])  // There it is!
                        {
                            p = j;
                            break;
                        }
            }
            return flags;
        }
    }
}

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.

Page 1 of 1

← June 2013 →

S	M	T	W	T	F	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

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!

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]

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]

My Blog Links

Syndicate my Blog (RSS)
Archive