# Thread: Beginner level issue: next prime number

1. ## Beginner level issue: next prime number

Hi all!

New member here. Recently started programming in C, and it's my first time programming. I've been trying to solve this exercise for days and I can't manage to make it work, so here I come desperately coming for some help!

The point of it is, given a number (ex: nb = 8), the function should return the next prime number, 11 in this case. In case you introduce an already prime number, like 7, it should give you that same number instead.

This is what I've done so far:

I have no idea where I may have messed it up. 8 returns me 1, but 9 returns me 11. 14 returns me 1, but 15 returns me 17.

Thanks!

2. Are you sure you're checking for primes?

3. Well we can't test your code because you posted a PICTURE of it.

Copy/paste your code and place code tags around it.
[code]
[/code]

4. > I have no idea where I may have messed it up. 8 returns me 1, but 9 returns me 11. 14 returns me 1, but 15 returns me 17.

Write down your code and dry run it in your head/paper a few times and you'll see the mistake in the logic, however its nothing to worry about. Some of the simplest mistakes happen from the best of us.... Also, next time, please post your code using the CODE tag enclosed within []. It makes it easy for others to copy the code and debug it.

I do have a solution ready that I just wrote but I would advise you to try solving the problem statement yourself before looking at any solutions. Proceed, if you want to.

Code:

Code:
```int NextPrime (int N)
{
bool found = false;

while(!found)
{
N++;
found = isPrime(N);
}

return N;
}

bool isPrime (int N)
{
for(int i = 2; i <= (N/2); i++)
{
if(N % i == 0)
return false;
}
return true;
}```

This code should give you the exact next Prime Number but as you mentioned an input of 7 should yield you a 7, I have the code for that too ready. If you have looked up the above solution, then changing the position of one line of code and editing another will yield you the expected output. You could think of what should be done yourself as a question for practice but I'll share the solution anyway in case you succeed and want to do a comparison...

The way I've done it is only one out of several approaches and this may be inefficient but its the best I could come up with it in a very interval of time. Good luck!

Code:

Code:
```int NextPrime(int N)
{
bool found = false;

while(!found)
{
found = isPrime(N);
N++;
}

return (N - 1);
}

bool isPrime(int N)
{
for(int i = 2; i <= (N/2); i++)
{
if(N % i == 0)
return false;
}
return true;
}```

5. Originally Posted by Zeus_
> I have no idea where I may have messed it up. 8 returns me 1, but 9 returns me 11. 14 returns me 1, but 15 returns me 17.

Write down your code and dry run it in your head/paper a few times and you'll see the mistake in the logic, however its nothing to worry about. Some of the simplest mistakes happen from the best of us.... Also, next time, please post your code using the CODE tag enclosed within []. It makes it easy for others to copy the code and debug it.

I do have a solution ready that I just wrote but I would advise you to try solving the problem statement yourself before looking at any solutions. Proceed, if you want to.

Code:

Code:
```int NextPrime (int N)
{
bool found = false;

while(!found)
{
N++;
found = isPrime(N);
}

return N;
}

bool isPrime (int N)
{
for(int i = 2; i <= (N/2); i++)
{
if(N % i == 0)
return false;
}
return true;
}```

This code should give you the exact next Prime Number but as you mentioned an input of 7 should yield you a 7, I have the code for that too ready. If you have looked up the above solution, then changing the position of one line of code and editing another will yield you the expected output. You could think of what should be done yourself as a question for practice but I'll share the solution anyway in case you succeed and want to do a comparison...

The way I've done it is only one out of several approaches and this may be inefficient but its the best I could come up with it in a very interval of time. Good luck!

Code:

Code:
```int NextPrime(int N)
{
bool found = false;

while(!found)
{
found = isPrime(N);
N++;
}

return (N - 1);
}

bool isPrime(int N)
{
for(int i = 2; i <= (N/2); i++)
{
if(N % i == 0)
return false;
}
return true;
}```
Thanks for the reply! I'll paste the code next time, I didn't even realize about that ^^'

The only problem I have with your code is that I should be making it in only one function. I even thought it was impossible to do with only one function, but I'll take a look at how you did it and find how to make it in only one. Also I didn't use a bool type of variable so far, so I'll check that too. Thank you so much!

6. Originally Posted by TheMoogletPiper
Thanks for the reply! I'll paste the code next time, I didn't even realize about that ^^'

The only problem I have with your code is that I should be making it in only one function. I even thought it was impossible to do with only one function, but I'll take a look at how you did it and find how to make it in only one. Also I didn't use a bool type of variable so far, so I'll check that too. Thank you so much!
Do you know what a prime number is?

7. Originally Posted by Hodor
Do you know what a prime number is?
Well, a number that only when divided by itself (and 1) gives you 0 residue.

Basically what I'm trying to do is, in the first while, check that the number doesn't give you 0 residue starting by 2 and going up, and if it reaches that same number, return it.

Then next while, in case it's already divisible by 2, go to the next number, and basically do the same loop as before.

There's definitely something going over my head, cause it's not working properly, but I don't know if it's because of my poor programming skills so far or because I'm just too dumb to see it.

8. Originally Posted by TheMoogletPiper
Well, a number that only when divided by itself (and 1) gives you 0 residue.

Basically what I'm trying to do is, in the first while, check that the number doesn't give you 0 residue starting by 2 and going up, and if it reaches that same number, return it.

Then next while, in case it's already divisible by 2, go to the next number, and basically do the same loop as before.

There's definitely something going over my head, cause it's not working properly, but I don't know if it's because of my poor programming skills so far or because I'm just too dumb to see it.
Yes, but divisible by 2 without a remainder is not what a prime number is. I don't think your problem is poor programming skills, but a poor understanding of prime numbers. 12, for example, is divisible by 2 without a remainder but it's not a prime number. 12 is a composite number (it is 2 x 2 x 3 ... these 3 numbers are primes; i.e. 12 is a combination of prime factors/numbers so it's not a prime number). I only asked this because the code in your first post doesn't determine what a prime number is at all, and your divisible by 2 comment kind of reflects that misunderstanding.

So, the first thing I'd do if I was you would be to read about prime numbers. @Zeus_ has already given code that has a big hint. You shouldn't have a big cascade of if statements like you do in the picture you posted either. Your first task I think is to write some code to test whether or not a number is prime or not. @Zeus_ used a function, but it doesn't have to be a function if you aren't allowed to use more than one function. You start from your candidate number plus one and then keep incrementing until you find a prime. That's one loop, not a whole bunch of loops.

9. Originally Posted by TheMoogletPiper
Well, a number that only when divided by itself (and 1) gives you 0 residue.

Basically what I'm trying to do is, in the first while, check that the number doesn't give you 0 residue starting by 2 and going up, and if it reaches that same number, return it.
Did you notice that the only even prime number is 2? Any other even number is divisible by 2. So if your number isn't 2 (and it is odd) you need to check for the odd divisors. And you don't need to check half of the range, but only until the even number near the square root of N (think abour it for a while!).

Here's an interesting implementation for study:
Code:
```/* prime.c */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <errno.h>
#include <limits.h>

static int isPrime( unsigned int );
static unsigned int isqrt( unsigned int );

int main( int argc, char **argv )
{
unsigned long n;
char *p;

// I'll ignore more than 1 argument!
if ( ! *++argv )
{
fputs( "Usage: prime <number>\n", stderr );
return EXIT_FAILURE;
}

errno = 0;
n = strtoul( *argv, &p, 10 );

// I'll accept only numeric argument in range... (no spaces).
if ( errno == ERANGE || *p != '\0' )
{
error:
fputs( "ERROR: Invalid argument\n", stderr );
return EXIT_FAILURE;
}

// I'll accept only argument in 'unsigned int' range.
if ( n > UINT_MAX )
goto error;

printf( "%lu %s prime.\n",
n,
isPrime( n ) ? "is" : "isn't" );

return EXIT_SUCCESS;
}

int isPrime( unsigned int n )
{
unsigned int sqrt_, i;

// 1, 2 and 3 are always primes (special cases).
if ( n <= 3 )
return 1;

// if n is even, isn't prime for sure!
if ( !( n & 1 ) )
return 0;

// Calculates the upper limit and must be odd.
sqrt_ = isqrt( n );
if ( !( sqrt_ & 1 ) )
sqrt_--;

// We need to check only odd divisors starting from 3.
for ( i = 3; i <= sqrt_; i += 2 )
{
// if n is divisible by any of them, not a prime!
if ( !( n % i ) )
return 0;
}

// if we get here, it is a prime.
return 1;
}

// Interesting binary algorithm to extract integer square root.
// This is, essentially, a binary search algorithm.
// Use this to avoid using floating point sqrt() - (and it is, probably, faster).
// Stolen from wikipedia: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots
unsigned int isqrt( unsigned int num )
{
unsigned int res = 0;
unsigned int bit = 1U << 30;

while ( bit > num )
bit >>= 2;

while ( bit )
{
if ( num >= res + bit )
{
num -= res + bit;
res = ( res >> 1 ) + bit;
}
else
res >>= 1;

bit >>= 2;
}

return res;
}```
A small test:
Code:
```\$ cc -O2 -march=native -o prime prime.c
\$ time ./prime 4294967291
4294967291 is prime.

real    0m0,002s
user    0m0,002s
sys    0m0,000s```

10. Thanks for the replies!

My point with ''if it's divisible by 2'' is to already discard that number and go check the next one.
But I'll take a deep look at all your hints and try to figure it out!

Cheers

11. > The only problem I have with your code is that I should be making it in only one function. I even thought it was impossible to do with only one function, but I'll take a look at how you did it and find how to make it in only one. Also I didn't use a bool type of variable so far, so I'll check that too. Thank you so much!

What can be done using 10 different functions can be done using a single function too. As a matter of fact you can do all your code just in main() and it'd still work essentially using no extra functions (but that's bad practice as it destroys the point of modularity enforcement). My point is that I have used two functions but you can write similar code in main() too and it'll still work, without using any other functions (except main(), ofcourse).

Here's the code for achieving the same result using only one function:

Code:
```int NextPrime (int N)
{
bool found = false;

while(!found)
{
for(int i = 2; i <= (N/2); i++)
{
if(!(N % i == 0))
found = true;
}
N++;
}

return (N - 1);
}```

Essentially, if you copy-paste this code in your main() function, you wouldn't even need the function call to NextPrime()...

12. Originally Posted by flp1969
Code:
```// Interesting binary algorithm to extract integer square root.
// This is, essentially, a binary search algorithm.
// Use this to avoid using floating point sqrt() - (and it is, probably, faster).
// Stolen from wikipedia: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots
unsigned int isqrt( unsigned int num )
{
unsigned int res = 0;
unsigned int bit = 1U << 30;

while ( bit > num )
bit >>= 2;

while ( bit )
{
if ( num >= res + bit )
{
num -= res + bit;
res = ( res >> 1 ) + bit;
}
else
res >>= 1;

bit >>= 2;
}

return res;
}```
@flp1969 yeah that's an interesting implementation. I'd change

Code:
`unsigned int bit = 1U << 30;`
to something more like
Code:
```unsigned int bit = (~(UINT_MAX >> 1)) >> 1;
or
unsigned int bit = (~(0U >> 1) >> 2) + 1;```
so that the size of unsigned int is not assumed, but I understand that it's from Wikipedia and that might not be very clear. Anyway, that's not the reason for my post. A few years ago I implemented quite a few of these algorithms because the CPU I was using did not have a FPU. On my computer (x86_64 and using gcc with no optimisations and also with -O2 and -O3), the following function

Code:
```unsigned int isqrt2( unsigned int num )
{
return sqrt(num);
}```
is about 7-8 times faster (for finding the square root of the numbers0 0 through to 1073741822) than the implementation from Wikipedia (presumably because glibc uses FSQRT or something.. I guess I could look hahah). I don't have an ARM or anything handy at the moment but it would be interesting to test. Nevertheless these algorithms are handy to know

Edit: I looked at a glibc mirror

glibc/sysdeps/x86_64/fpu/e_sqrt.c uses FSQRT (the other fpu architectures use built-in sqrt as well -- at least all the ones I checked in sysdeps/*/fpu anyway)
glibc/sysdeps/ieee754/dbl-64/e_sqrt.c provides a fallback sqrt function

13. Edit to the above:

glibc/sysdeps/x86_64/fpu/e_sqrt.c uses FSQRT (the other fpu architectures use built-in sqrt as well -- at least all the ones I checked in sysdeps/*/fpu anyway)
glibc/sysdeps/ieee754/dbl-64/e_sqrt.c provides a fallback sqrt function
I'm now not sure now if gcc uses those fpu versions of the functions by default but I won't have time to look more until I get home. If gcc doesn't use the FPU implementations by default then the glibc/sysdeps/ieee754/dbl-64/e_sqrt.c implementation is blazingly fast.

Edit: ok, I'm pretending I'm on lunch.

Stepping into sqrt() I see that it makes a single call to __sqrt_finite
Code:
`jmpq   0x7ffff7e8f0b0 <__sqrt_finite>`
Stepping into that I see:
Code:
```Dump of assembler code for function __sqrt_finite: (addresses removed; not relevant)
endbr64
sqrtsd %xmm0,%xmm0
retq```
which is from glibc/sysdeps/x86_64/fpu/e_sqrt.c (I'm beginning to think that the glibc source tree is hard to read lol... easier to just use gdb and then look at the source)

So, yeah, I guess that's why it's fast

14. Yep... you could use sqrt(), but the ideia is not to use libm and floating point sqrt is slow! And has a minor strange implementation on GCC:
Code:
```; from:
;   unsigned int isqrt( unsigned int n ) { return sqrt(n); }
;
; Why sqrt@PLT is called in some cases? To set errno!
isqrt:
mov       edi, edi
pxor      xmm0, xmm0
pxor      xmm2, xmm2
cvtsi2sdq xmm0, rdi
ucomisd   xmm2, xmm0
sqrtsd    xmm1, xmm0
ja        .L10
cvttsd2si rax, xmm1
ret
.L10:
sub       rsp, 24
movsd     [rsp+8], xmm1
call      sqrt@PLT
movsd     xmm1, [rsp+8]
cvttsd2si rax, xmm1
ret```
I've already inform a tiny bug with sqrt() to GCC Bugzilla (extracting the square root of negative numbers will always result in NaN, but this code do it TWICE!). You can always use -ffast-math option to straighten things:

Code:
```; Same function:
isqrt:
mov       edi, edi
pxor      xmm0, xmm0
cvtsi2sdq xmm0, rdi
sqrtsd    xmm0, xmm0
cvttsd2si rax, xmm0
ret```
But you loose errno.

Anyway... fsqrt takes 10~23 clock cycles, so for modern processors (since Pentium 4), SSE is disirable since sqrtsd takes 16 (the conversions takes 5). The routine using just integer calculations CAN BE faster than using floating point.

There is a problem with precision too... To extract the square root of a 32 bits value you need more then 24 bits precision (float), so you need a double (53 bits precision), which will require a 64 bits storage space (RDI and RAX)... more clock cycles lost due to REX prefix and, in some cases, cache side effects.

Of course, you can simply calculate the square root using sqrt() function, if all of this doesn't matter...

And, I agree. The more portable approach is desirable.

15. Here's one example using sqrt() and the "binary" isqrt():
Code:
```/* sqrt-test.c */
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <limits.h>
#include <math.h>
#include "../../src/cycle_counting.h"

static unsigned int isqrt( unsigned int );

int main( int argc, char **argv )
{
counter_T c1, c2;
unsigned long n;
unsigned int a, b;
char *p;

// I'll ignore more than 1 argument!
if ( ! *++argv )
{
fputs( "Usage: prime <number>\n", stderr );
return EXIT_FAILURE;
}

errno = 0;
n = strtoul( *argv, &p, 10 );

// I'll accept only numeric argument in range... (no spaces).
if ( errno == ERANGE || *p != '\0' )
{
error:
fputs( "ERROR: Invalid argument\n", stderr );
return EXIT_FAILURE;
}

// I'll accept only argument in 'unsigned int' range.
if ( n > UINT_MAX )
goto error;

c1 = BEGIN_TSC();
a = sqrt( n );
END_TSC( &c1 );

c2 = BEGIN_TSC();
b = isqrt( n );
END_TSC( &c2 );

printf( " sqrt( %1\$lu ) = %2\$u (%3\$lu cycles)\n"
"isqrt( %1\$lu ) = %4\$u (%5\$lu cycles)\n",
n, a, c1, b, c2 );

return EXIT_SUCCESS;
}

// Interesting binary algorithm to extract integer square root.
// This is, essentially, a binary search algorithm.
// Use this to avoid using floating point sqrt() - (and it is, probably, faster).
// Stolen from wikipedia: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots
unsigned int isqrt( unsigned int num )
{
unsigned int res = 0;
unsigned int bit = 1U << 30;

while ( bit > num )
bit >>= 2;

while ( bit )
{
if ( num >= res + bit )
{
num -= res + bit;
res = ( res >> 1 ) + bit;
}
else
res >>= 1;

bit >>= 2;
}

return res;
}```
Compiling (with optimization) and running in an i7-4770:
Code:
```\$ cc -O2 -o sqrt-test sqrt-test.c
\$ ./sqrt-test
\$ ./sqrt-test 1000000000
sqrt( 1000000000 ) = 31622 (537 cycles)
isqrt( 1000000000 ) = 31622 (497 cycles)```
isqrt() is 7% faster.
```\$ gcc -O2 -ffast-math -o sqrt-test sqrt-test.c