C/C++ Solving Prime Number Code Error in C++

  • Thread starter Thread starter chaoseverlasting
  • Start date Start date
  • Tags Tags
    C++ Code Prime
AI Thread Summary
The discussion centers on troubleshooting a C++ program designed to check if a number is prime. Key issues identified include the use of an uninitialized float variable for the input number, which leads to errors when performing modulus operations. The conversation emphasizes that prime number checks should utilize integer types, not floating-point types, due to the limitations and inaccuracies associated with floats. Suggestions include using integer types like uint64_t or int64_t for handling large numbers, and the need for external libraries for arbitrary precision integers if necessary. The thread also touches on the importance of correctly handling floating-point numbers, particularly when converting between types, as precision can be lost. Overall, the consensus is to avoid using floats for prime checking and to use appropriate integer types to ensure accurate calculations.
chaoseverlasting
Messages
1,050
Reaction score
3
I was writing a program to find if a given number is prime or not. I can't figure out what the error is.
Code:
/* To check if a number is prime*/

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    float a;
    int p,i,f=0;


    p=sqrt(a);
    
    if(a % 2==0)          // Shows an error: Cant convert float and int types to binary %
              cout<<"\nNot a prime";
    else    
            for(i=3;i<=p;i+=2)
                     if(a%i==0)  //Same error here
                                break;
                   
       if(i==p||i==(p+1))
          cout<<"\nThe number is a prime";
       else
           cout<<"\nThe number is not a prime";
           
     return 0;
}
 
Technology news on Phys.org
For starters you are trying to take the square root of an uninitialized number in this statement: p = sqrt(a);

Next, you shouldn't be working with floating point types (float or double) if you're trying to determine whether a number is prime. When we talk about numbers being prime, we are talking about integer numbers, such as 14, 37, and so on, and not about floating point numbers such as 6.2, 9.37, and so on.
 
Thank you. I can't believe I missed that. I am using floats for the range. Another thing, floats some times display values in the exponential format, how can you display the whole number?
 
Your program should not even compile. You should be getting an error message along the lines of ‘Illegal use of Floating Point’.

Don't use float for this problem.
 
Why shouldn't it compile?
 
Because of your use of the modulus operator with a float.
 
Is there a way to store large numbers (> 4 million) as integers?
 
chaoseverlasting said:
Is there a way to store large numbers (> 4 million) as integers?
Microsoft C++ includes a "decimal" class which stores 96 bit (28 decimal digit) integers.

Beyond that, you'd need an extended precision math library, like apfloat, or implement one yourself.

Modulo won't work with floating point numbers in c, instead you have to do it manually like this:

Code:
#include <stdio.h>
#include <math.h>

static float dividend, divisor, int_quotient, remainder;

int main()
{
    dividend  = 2.3;
    divisor   = 1.2;
    int_quotient  = floor(dividend/divisor);
    remainder = dividend - (divisor*int_quotient);
    printf("%10.5f\n", remainder);
    return(0);
}
 
Use uint64_t or int64_t. (Alternately I think most compilers will let you just say "long long" as an alias for int64_t). This will be portable and will raise your ceiling to 2^64 rather than 2^32.

If you need arbitrary magnitude integers you will need an external library as roger suggests. The magic word to look for to find the integer version of such a library is "bignum".
 
  • #10
I had tried to download such a library before but I couldn't figure out how to make it work. Could someone guide me through the process or direct me to a web resource that could help me out?

Also with the modulo, I don't need the floating point digit, just the integer remainder. Would the modulo just treat the floats as ints?
 
  • #11
chaoseverlasting said:
Also with the modulo, I don't need the floating point digit, just the integer remainder. Would the modulo just treat the floats as ints?

I'd have to check but I think if you use the % operator on a float it's just a compile error. If you want floating point modulo use the modf() or fmod() functions in math.h. If you want the integer remainder and can discard the floating point part, cast to int and then use %.
 
  • #12
chaoseverlasting said:
Is there a way to store large numbers (> 4 million) as integers?

I've used the MIRACL library for large integer math and it has worked well. It's free to download and you can use it for free in any non-commercial program.
 
  • #13
I'm not sure you're aware of this, but floating point doesn't store exact numbers. Consider this program
Code:
#include <iostream>
using namespace std;
int main()
{
  unsigned int x = 1234567890u; // Assume unsigned int is large enough to hold this number[/color]
  float y = x;
  x = y;
  cout << x << endl; // Outputs 1234567936[/color]
}
(I'm assuming an int is a 32-bit data type or bigger. Use uint32_t if you're paranoid)
(I used Microsoft's Visual Studio C++ compiler)

Again, using Microsoft's compiler (and their 64-bit integral type -- use uint64_t if you can, for portability. If you have neither, unsigned long long is probably this type):
Code:
int main(){
  unsigned __int64 x = 12345678901234567890;
  double y = x;
  x = y;
  cout << x << endl; // Outputs 9223372036854775808[/color]
}
This last one actually surprises me greatly -- I would have thought it would have had much better precision. I wonder what went wrong?
 
  • #14
Hurkyl said:
Code:
int main(){
  unsigned __int64 x = 12345678901234567890;
  double y = x;
  x = y;
  cout << x << endl; // Outputs 9223372036854775808[/color]
}
This last one actually surprises me greatly -- I would have thought it would have had much better precision. I wonder what went wrong?
Works for me:
Code:
#include <iostream>
#include <stdint.h>
int main(){
  uint64_t x = 12345678901234567890ull;
  double y = x;
  x = y;
  std::cout << x << "\n"; // Outputs 12345678901234567168[/color]
}

My guess as to what went wrong: The unqualified constant 12345678901234567890 isn't handled correctly by Microsoft C++. gnu c++ complained about it but still output the correct value. Qualifying the constant as 12345678901234567890ull eliminates the warning.

Also note that the double value is still not quite correct, not surprising. That unsigned long long integer has too many digits to be fully representable in a double.
 
  • #15
In my test I printed x before I assigned it to y and it printed what I expected. Of course, it's definitely right that it should have printed a truncated value. I wonder if I found an actual bug where the optimizer figured out it could print the constant before it triggered the truncation?

edit nope. Changing the suffix to ull didn't affect anything.
 
  • #16
Oooh, it converts the number to 263. It seems that this compiler, or maybe my hardware, rounds larger floating point numbers to 263, even if they would fit in a 64-bit integer. :frown:

And shame on me for not instantly recognizing 263. :redface:
 
  • #17
So I tried running this in the debugger (in VS2008) and looking at the disassembly output.

The culprit appears to be the line x = y; If you print out y before that line, it appears to be a roughly accurate representation of the number you wanted.

The disassembly for x=y is...

004115D1 fld qword ptr [y]
004115D4 call @ILT+540(__ftol2) (411221h)
004115D9 mov dword ptr [x],eax
004115DC mov dword ptr [ebp-8],edx

__ftol2 is of course MS's float to long routine. I wonder-- is it possible that it doesn't understand unsigned numbers?!
 
Back
Top