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

[Nebur]

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,

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

[Nebur]

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.

[Josue Molina]

Line 15 should be i * i <= n.

[Josue Molina]

We posted at the same time. ;-)

[GRex2595]

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.

[Nebur]

Really?

I thought recursion meant that the function calls itsself but i was not aware of the different types of recursion.

[GRex2595]

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?

[Josue Molina]

GRex2595, +1.

This site should have up-votes. :-)

[JLBorges]

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

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

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