Thread: Beginner level issue: next prime number

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    4

    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:


    Beginner level issue: next prime number-c6a38f01360447f9f9406c9e5e9fc6d4-png

    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. #2
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,456
    Are you sure you're checking for primes?

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,484
    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]
    // paste your code here, directly from your code editor.
    [/code]
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    102
    > 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. #5
    Registered User
    Join Date
    Oct 2019
    Posts
    4
    Quote Originally Posted by Zeus_ View Post
    > 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. #6
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,456
    Quote Originally Posted by TheMoogletPiper View Post
    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. #7
    Registered User
    Join Date
    Oct 2019
    Posts
    4
    Quote Originally Posted by Hodor View Post
    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. #8
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,456
    Quote Originally Posted by TheMoogletPiper View Post
    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. #9
    Registered User
    Join Date
    Feb 2019
    Posts
    533
    Quote Originally Posted by TheMoogletPiper View Post
    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
    Last edited by flp1969; 2 Weeks Ago at 07:40 AM.

  10. #10
    Registered User
    Join Date
    Oct 2019
    Posts
    4
    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. #11
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    102
    > 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()...
    Last edited by Zeus_; 2 Weeks Ago at 12:59 PM.

  12. #12
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,456
    Quote Originally Posted by flp1969 View Post
    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
    Last edited by Hodor; 2 Weeks Ago at 10:01 PM.

  13. #13
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,456
    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
    Last edited by Hodor; 2 Weeks Ago at 11:16 PM.

  14. #14
    Registered User
    Join Date
    Feb 2019
    Posts
    533
    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.

  15. #15
    Registered User
    Join Date
    Feb 2019
    Posts
    533
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help needed for a programme .. (beginner level )
    By dineshpabbi10 in forum C Programming
    Replies: 4
    Last Post: 06-04-2015, 10:48 PM
  2. Replies: 3
    Last Post: 12-02-2014, 10:11 AM
  3. Help! beginner level question
    By seking10788 in forum C Programming
    Replies: 6
    Last Post: 07-07-2011, 08:15 AM
  4. Can someone help me with this beginner-level program?
    By matthayzon89 in forum C Programming
    Replies: 5
    Last Post: 05-09-2010, 11:00 AM
  5. Replies: 3
    Last Post: 03-29-2005, 04:24 PM

Tags for this Thread