### Check if a number and the sum of its digits are prime

Hi everybody,

I am trying to do a program that checks if a number is primer, and the sum of its digits, and the sum of the sum of its digits, and so on until we get to a sum which is smaller than 10 (one digit).

I have to do it recursively, and as you can see in the code I use two functions. First one to sum the digits of n, and then another one to check if that sum is prime and if it isn't,
 ``12345678910111213141516171819202122232425262728`` ``````#include using namespace std; int sum_of_digits (int n) { if (n < 10) return n; else return n%10 + sum_of_digits(n/10); } bool is_perfect_prime (int n) { if (n < 10) { if (n == 2 or n == 3 or n == 5 or n == 7) return true; else return false; } for (int i = 2; i*i < n; ++i) { //CHECK IF THE NUMBER IS PRIME if (n%i == 0) return false; } return is_perfect_prime(sum_of_digits(n)); //IF IT ISN'T REPEAT THE PROCESS WITH THE SUM OF ITS DIGITS } int main () { int n; while (cin >> n) { if(is_perfect_prime(n)) cout << "SI" << endl; else cout << "NO" << endl; } }``````

The code isn't very complicated, but there are some values for the ones it doesen't work.

>>>>PLEASE: If you could give me a hint, rather than the solution it would be very appreciated, I am here to learn.

Thanks!
I already solved it, the problem was in the for iteration, the "<" symbol should have been "<=" in the case the divisor is exactly the square root of n.
Line 15 should be i * i <= n.
We posted at the same time. ;-)
This is going to sound really bad.

Your isPerfectPrime function isn't actually recursive. It'll probably be ok to turn it in like it is, but your type of recursion is called tail-end recursion, and it is slightly inefficient because it could be used as an iteration rather than recursion.

Now that I've told you it doesn't count as recursion, I don't actually have a solution for that at this time. If you don't have to use recursion on that function, it should be turned into a loop. The other one seems fine, though.
Really?

I thought recursion meant that the function calls itsself but i was not aware of the different types of recursion.
I actually just reread my chapter on recursion in my Java book the other day, so that's why I'm saying this. Iteration is less resource expensive than recursion.

Tail-end recursion is recursion where you call the function within itself after you have performed all the operations you're going to perform in the function. Essentially what you're doing is resetting everything and starting over again, but instead of going back to the top through iteration, you're adding your function to the stack, then starting over again. My book says that a good compiler will look for that and change your function to an iteration, but you can't rely on that.

Your other function, however is recursion in the best way. My book says that a good recursive function simplifies the function without any drastic loss in efficiency. Does your isPerfectPrime function simplify the code? Is there loss in efficiency?
Last edited on
GRex2595, +1.

This site should have up-votes. :-)
> your type of recursion is called tail-end recursion, and it is slightly inefficient
> because it could be used as an iteration rather than recursion.
> I actually just reread my chapter on recursion in my Java book the other day, so that's why I'm saying this.

C++ is not Java; C++ compilers are not Java compilers.

Unless there are too many calls to non-trivial destructors of temporary objects (and there are none in the tail-recursive function under discussion), C++ compilers routinely perform tail-call-optimization.
http://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization

If a tail-call-recursive function would simplify the code, write it that way; without fear of degradation in performace. In any event, do not even think about premature low-level optimization, till you have profiled the code and discovered a performance bottleneck in the critical path. Make high level design decisions like choice of data structures and algorithms; write the cleanest, clearest, most transparent code that you possibly can; and leave low-level optimization decisions to the compiler - it is pretty good at doing that.

Check it out:
 ``1234567891011121314151617`` ``````int sum_of_digits (int n) { if (n < 10) return n; else return n%10 + sum_of_digits(n/10); } bool is_perfect_prime (int n) { if (n < 10) { if (n == 2 or n == 3 or n == 5 or n == 7) return true; else return false; } for (int i = 2; i*i < n; ++i) { //CHECK IF THE NUMBER IS PRIME if (n%i == 0) return false; } return is_perfect_prime(sum_of_digits(n)); //IF IT ISN'T REPEAT THE PROCESS WITH THE SUM OF ITS DIGITS }``````

compiled with: `g++ -std=c++11 -pedantic-errors -Wall -Wextra -O3 -c -S test.cc`

`is_perfect_prime()` is transformed into a completely iteraive version
(with an inlined iterative `sum_of_digits()` thrown in as a bonus):

test.S
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106`` `````` .file "test.cc" .text .p2align 4,,15 .globl __Z13sum_of_digitsi .def __Z13sum_of_digitsi; .scl 2; .type 32; .endef __Z13sum_of_digitsi: pushl %esi pushl %ebx movl 12(%esp), %ecx xorl %ebx, %ebx cmpl \$9, %ecx jle L2 movl \$1717986919, %esi .p2align 4,,7 L3: movl %ecx, %eax imull %esi movl %ecx, %eax sarl \$31, %eax sarl \$2, %edx subl %eax, %edx movl %edx, %eax leal (%edx,%edx,4), %edx addl %edx, %edx subl %edx, %ecx movl %ecx, %edx movl %eax, %ecx addl %edx, %ebx cmpl \$9, %eax jg L3 L2: leal (%ebx,%ecx), %eax popl %ebx popl %esi ret .p2align 4,,15 .globl __Z16is_perfect_primei .def __Z16is_perfect_primei; .scl 2; .type 32; .endef __Z16is_perfect_primei: pushl %esi movl \$1717986919, %esi pushl %ebx movl 12(%esp), %ebx cmpl \$9, %ebx jle L9 L11: cmpl \$4, %ebx jle L13 testb \$1, %bl je L20 movl \$2, %ecx jmp L14 .p2align 4,,7 L15:is_perfect_prime movl %ebx, %eax cltd idivl %ecx testl %edx, %edx je L20 L14: addl \$1, %ecx movl %ecx, %eax imull %ecx, %eax cmpl %ebx, %eax jl L15 L13: xorl %ecx, %ecx .p2align 4,,7 L18: movl %ebx, %eax imull %esi movl %ebx, %eax sarl \$31, %eax sarl \$2, %edx subl %eax, %edx movl %edx, %eax leal (%edx,%edx,4), %edx addl %edx, %edx subl %edx, %ebx movl %ebx, %edx movl %eax, %ebx addl %edx, %ecx cmpl \$9, %eax jg L18 addl %ecx, %ebx cmpl \$9, %ebx jg L11 L9: leal -2(%ebx), %eax cmpl \$1, %eax setbe %dl cmpl \$5, %ebx sete %al orb %dl, %al jne L21 cmpl \$7, %ebx sete %al jmp L21 .p2align 4,,7 L20: xorl %eax, %eax L21: popl %ebx popl %esi ret .ident "GCC: (GNU) 4.9.0 20130901 (experimental)"``````
Last edited on
Topic archived. No new replies allowed.