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

Are you sure you're checking for primes?

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

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!

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?

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.

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.

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

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]
  add       rsp, 24
  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.

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.
Now, add -ffast-math option:

Code:

$ gcc -O2 -ffast-math -o sqrt-test sqrt-test.c
$ ./sqrt-test 1000000000
 sqrt( 1000000000 ) = 31622 (109 cycles)
isqrt( 1000000000 ) = 31622 (553 cycles)

So, without the proper optimizations, isqrt() is, indeed, faster.