Subscribe to gabehabe's on-topic ramblings

## Circular Primes

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.

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

### 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;
}
```
0

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

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

Care to share?
0

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

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

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

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

S M T W T F S
123
45678910
11121314151617
1819 20 21222324
25262728293031

### 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!

### 0 user(s) viewing

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

### gabehabe's off-topic ramblings

lol, my other blog died a horrible lonely death. Ah well.

### Contact Me

e-mail: [email protected]