C - Find Prime number

Question

This is my prime number function and I have a problem.
Why does it return 0 when I pass it 2147483647?

int     ft_is_prime(int nb)
{
  if (nb<2)
    return (0);
  else if (nb==2)
    return (1);
  else if (nb%2==0)
    return (0);
  else 
  {
    int i=3;
    int carre=9;
    while (carre <= nb)
    {
        if (nb % i == 0)
            return (0);
        carre=carre+4*i+4;
        i=i+2;
    }
    return (1);
  }
}

c `int` is a 16bit datatype, you're trying to stuff a 32bit value into it. — Marc B, Aug 11 '15 at 14:28
@MarcB But sir, isn't it environment dependent? It _can_ be 32 bits also, and mostly is (on `gcc`). — Sourav Ghosh, Aug 11 '15 at 14:29
@MarcB: `int` is not a single size, it can be 16-bit, it can be 32-bit, etc.... — Veltas, Aug 11 '15 at 14:29
Signed integer overflow somewhere? And that is [undefined behavior](http://stackoverflow.com/a/4240878/440558). — Some programmer dude, Aug 11 '15 at 14:30
`if (nb % i == 0) return (0);` : `2147483647 % 2147483647 == 0 then return 0;` — BLUEPIXY, Aug 11 '15 at 14:38
@Veltas Optimization might refer to algorithmic optimization. — Eugene Sh., Aug 11 '15 at 14:46
@EugeneSh.: it's still irrelevant to the question, there are well-documented better algorithms for prime number determination. OP clearly isn't interested in this, and is asking about their specific problem. — Veltas, Aug 11 '15 at 14:49

Frederic Brégier · Accepted Answer · 2015-08-11T16:58:41.717

As @Eugene-Sh said, there is an overflow while computing carre.

Also, the standard int is at minimum 16bits. However most of compilers now make it 32bits. So at least you should check the limit, in order your code gets well in all the ways.

Change to long long to ensure you will have good result, both for carre and nb, such that you got 64 bits. But it is only half of the path. as said in a comment, you could still have an overflow when you go over this limit.

So something like this, without changing type:

int max = INT_MAX; // from limits.h
int maxsqrt = sqrt(INT_MAX); // cast to int, such that maxsqrt² is the max square
if (maxsqrt % 2 == 0)
   maxsqrt--; // only odd number considered
int maxcarre = maxsqrt*maxsqrt; // this is the max square (carre in french) for an odd INT

Then in your loop, you could now check if carre is the last one you can compute since maxcarre is the biggest one:

while (carre <= nb)
{
    if (nb % i == 0)
        return (0);
    if (carre >= maxcarre) // this is the last odd square we could compute before overflow
        return (-1); // if this -1 represents a "don't" know code for you
    carre=carre+4*i+4; // this compute the next square of an odd number 
    i=i+2;
}

I would recommend however to use at least long (and therefore changing max to LONG_MAX) in order to get more capacity and still in the range of the CPU (64 bits on modern compiler), or even long long since at least it is 64 bits on all compilers.

As @Veltas said: long is 64-bit on some 64-bit compiler implementations. It's not dependant on the OS. Also, IIRC Microsoft's VC++ uses 32-bit long on 64-bit as well.

Thanks to @Veltas, @EugeneSh. and other helping people for their precious feedback!

@FredericBrégier That's not the standard value, that's the standard **minimum** value (quoting: *Their implementation-defined values shall be equal or greater in magnitude (absolute value) to those shown, with the same sign. § 5.2.4.2.1, ISO/IEC 9899:201x*), most implementation use 32-bits `int`. — Holt, Aug 11 '15 at 14:45

score 0 · Answer 2 · answered Sep 11 '17 at 23:44

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
/* As we know 2,3,5,7,11..19....
What is prime number
A prime number (or a prime) is a natural
number greater than 1 that has no positive
divisors other than 1 and itself.
so the formula in if we have n numbers as a input
how we find the prime number ,the formula is
divisible by 2 ...n-1. so 3%2=1 then 3 is a
prime number,10%2=0 so 10 is not a prime number 
now 9%2=1 but 9%3=0 that is why we will make a 
condition of for loop that divisible 9 with all
the numbers from 2...9-1 and find out whether it 
divisible value is 0.    
*/
int main()
{
    int i,n,j;
 bool flag;
    printf("Enter the Range Number:");
    scanf("%d",&n);
        for(i=2;i<=n;i++)
        { bool flag=true;
            for(j=2;j<=i-1;j++) 
            {

                if (i%j==0){
            flag=false;
            break;}
            }
 if (flag==true)
                printf("%d\n",i);
            }

    return 0;

}

C - Find Prime number

2 Answers2