Prime number code, C++

[chaoseverlasting]

I was writing a program to find if a given number is prime or not. I cant figure out what the error is.


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

[Mark44]

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.

[chaoseverlasting]

Thank you. I cant believe I missed that. Im using floats for the range. Another thing, floats some times display values in the exponential format, how can you display the whole number?

[D H]

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.

[chaoseverlasting]

Why shouldnt it compile?

[Mark44]

Because of your use of the modulus operator with a float.

[chaoseverlasting]

Is there a way to store large numbers (> 4 million) as integers?

[rcgldr]

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:


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

[Coin]

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".

[chaoseverlasting]

I had tried to download such a library before but I couldnt 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 dont need the floating point digit, just the integer remainder. Would the modulo just treat the floats as ints?

[Coin]

Also with the modulo, I dont 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 %.

[chiro]

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.

[Hurkyl]

I'm not sure you're aware of this, but floating point doesn't store exact numbers. Consider this program

#include <iostream>
using namespace std;
int main()
{
unsigned int x = 1234567890u; // Assume unsigned int is large enough to hold this number
float y = x;
x = y;
cout << x << endl; // Outputs 1234567936
}

(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):
int main(){
unsigned __int64 x = 12345678901234567890;
double y = x;
x = y;
cout << x << endl; // Outputs 9223372036854775808
}
This last one actually surprises me greatly -- I would have thought it would have had much better precision. I wonder what went wrong?

[D H]

int main(){
unsigned __int64 x = 12345678901234567890;
double y = x;
x = y;
cout << x << endl; // Outputs 9223372036854775808
}
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:
#include <iostream>
#include <stdint.h>
int main(){
uint64_t x = 12345678901234567890ull;
double y = x;
x = y;
std::cout << x << "\n"; // Outputs 12345678901234567168
}

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.

[Hurkyl]

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.

[Hurkyl]

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:

[Coin]

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?!