C++

Forum

 
What is causing this code to run slowly?

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

#include <iostream>
#include <cmath>

using namespace std;

int new_value, amount = 1;

int rotate(int x)                         // Rotates each number passed to it and tests each permutation for primality.
{
    int count = 0, duplicate = x, exponent;
    while(count < number_of_digits(x))
    {
        exponent = number_of_digits(x) - 1;
        new_value = duplicate;
        new_value = (new_value / 10) + (new_value % 10) * pow(10, exponent);
        if(isprime(new_value) == false)
        break;
        duplicate = new_value;
        count++;
    }
    if(isprime(new_value) == true)
    {
        amount++;
        cout << amount << endl;
    }
}
Last edited on
ne555 (10692)
Do one thing and do it well. rotate() is overloaded.

Your isprime() takes O(n) (where n is the inputted number)
You need to traverse all the numbers O(n)
So the total complexity will be O(n^2). When n -> 1e6, that's quite big.
Pravesh Koirala (267)
Thing 1.
Project Euler problems are meant for learning and fun. You posting codes here might ruin the day for somebody else.

Thing 2.
You are using trial division for checking primes. This is extremely slow process. Consider Sieve of Eratosthenes

Thing 3.
Your rotating algorithm ain't good.
Try to come up with a more elegant algorithm

Thing 4.
You are continuously calling number_of_digits(x).
consider
1
2
 
int numdigit = number_of_digits(x);
while (count < numdigit)
MathematicsFanatic (18)
I deeply apologize. I clearly wasn't thinking about ruining it for someone else. And if you would, what are some of the limitations of my rotating algorithm?
Pravesh Koirala (267)
Would you like to see my code for the rotating algorithm?
MathematicsFanatic (18)
If you wouldn't mind. I would like to add that I did get the right answer! It only took about 2 hours is all! Also, I am just learning programming so I am looking forward to the joys in the near future!

Last edited on
Pravesh Koirala (267)
Hehe,, turns out my rotating code is EXACTLY the same as yours. Mine runs in 0.2 seconds.
But I will post it anyways. I've used Sieve of Eratosthenes to check primes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
int length(int num)
{
    int count=0;
    while (num!=0)
        {
            count++;
            num /= 10;
        }
        return count;
}
int isCircular(int P)
{
    int L=length(P)-1;
    if (L==0) return true;
    for (int i=1;i<=L;i++)
    {
        P=P%10*pow(10,L)+P/10;
        if (Sieve[P] != PRIME) return 0;
        Sieve[P] = !PRIME;
    }
    return P;
}
MathematicsFanatic (18)
Now that we are on a comical note, here is my first attempt at the rotating algorithm! I felt accomplished when I came up with the simpler version after more than an hour of thinking!
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
int rotate(int x)
{
    if(x >= 100000)
    {
        s0 = x / 100000; s1 = (x / 10000) % 10; s2 = (x / 1000) % 10; s3 = (x / 100) % 10; s4 = (x / 10) % 10; s5 = x % 10;
        for(int y = 0; y < 6; y++)
        {
            ps0 = s0; s0 = s5; s5 = s4; s4 = s3; s3 = s2; s2 = s1; s1 = ps0;
            value = (s0 * 100000) + (s1 * 10000) + (s2 * 1000) + (s3 * 100) + (s4 * 10) + ps0;
            if(s0 == 0 || s1 == 0 || s2 == 0 || s3 == 0 || s4 == 0 || s5 == 0)
            break;
            if(s0 % 2 == 0 || s1 % 2 == 0 || s2 % 2 == 0 || s3 % 2 == 0 || s4 % 2 == 0 || s5 % 2 == 0)
            break;
            if(isprime(value) == false)
            break;
        }
        if(isprime(value) == true)
        count++;
    }
    else if(x >= 10000)
    {
        s0 = x / 10000; s1 = (x / 1000) % 10; s2 = (x / 100) % 10; s3 = (x / 10) % 10; s4 = x % 10;
        for(int y = 0; y < 5; y++)
        {
            ps0 = s0; s0 = s4; s4 = s3; s3 = s2; s2 = s1; s1 = ps0;
            value = (s0 * 10000) + (s1 * 1000) + (s2 * 100) + (s3 * 10) + ps0;
            if(s0 == 0 || s1 == 0 || s2 == 0 || s3 == 0 || s4 == 0)
            break;
            if(s0 % 2 == 0 || s1 % 2 == 0 || s2 % 2 == 0 || s3 % 2 == 0 || s4 % 2 == 0)
            break;
            if(isprime(value) == false)
            break;
        }
        if(isprime(value) == true)
        count++;
    }
    else if(x >= 1000)
    {
        s0 = x / 1000; s1 = (x / 100) % 10; s2 = (x / 10) % 10; s3 = x % 10;
        for(int y = 0; y < 4; y++)
        {
            ps0 = s0; s0 = s3; s3 = s2; s2 = s1; s1 = ps0;
            value = (s0 * 1000) + (s1 * 100) + (s2 * 10) + ps0;
            if(s0 == 0 || s1 == 0 || s2 == 0 || s3 == 0)
            break;
            if(s0 % 2 == 0 || s1 % 2 == 0 || s2 % 2 == 0 || s3 % 2 == 0)
            break;
            if(isprime(value) == false)
            break;
        }
        if(isprime(value) == true)
        count++;
    }
    else if(x >= 100)
    {
        s0 = x / 100; s1 = (x / 10) % 10; s2 = x % 10;
        for(int y = 0; y < 3; y++)
        {
            ps0 = s0; s0 = s2; s2 = s1; s1 = ps0;
            value = (s0 * 100) + (s1 * 10) + ps0;
            if(s0 == 0 || s1 == 0 || s2 == 0)
            break;
            if(s0 % 2 == 0 || s1 % 2 == 0 || s2 % 2 == 0)
            break;
            if(isprime(value) == false)
            break;
        }
        if(isprime(value) == true)
        count++;
    }
    else if(x >= 10)
    {
        s0 = x / 10; s1 = x % 10;
        for(int y = 0; y < 2; y++)
        {
            ps0 = s0; s0 = s1; s1 = ps0;
            value = (s0 * 10) + ps0;
            if(isprime(value) == false)
            break;
        }
        if(isprime(value) == true)
        count++;
    }
    else
    {
        s0 = x;
        count++;
    }
}
Pravesh Koirala (267)
WOW! Seems like you had fun. :)
MathematicsFanatic (18)
HAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAH NO!! :{
wtf (670)
sorry to bother, but what is this code actually supposed to do anyway?
MathematicsFanatic (18)
The program is currently being designed to calculate the amount of circular primes below one million.
Last edited on
Pravesh Koirala (267)
@MathematicsFanatic
So? You got your answers right?
MathematicsFanatic (18)
Negative! I have not yet made use of the so called Sieve of Eratosthenes. I took a break and moved on to Problem 36 instead. Which is equally if not more engaging I might add! :D
Last edited on
Pravesh Koirala (267)
@mathematicsFanatic
I suggest you first solve this problem. You've got your rotating part right. So why not learn the Sieve. Its incredibly simple and exciting. I'm sure you will find it useful.
wtf (670)
ok. but what is rotate?
MathematicsFanatic (18)
Currently, my rotate function takes a value and rotates the digits around. Let's say I want to rotate the number 1397. The function would print out 1397, 7139, 9713, and 3971.
wtf (670)
ok. But why not also 1379, 1793, 1739, etc ec etc also? Or does that not have anything to do with a circular prime?

Lastly, what is a circular prime?

Again, sorry if it seems I'm hijacking this thread, it just whetted my curiosity. thats all. Thanks.
firedraco (6242)
Pravesh Koirala (267)
@wtf,,
if this has indeed whetted your curiosity, then I think you should check this site (if you haven't already)
http://www.projecteuler.net
Topic archived. No new replies allowed.