Register to reply 
C++ prime testing 
Share this thread: 
#1
Apr412, 03:28 PM

P: 642

Alright. I know how incredibly inefficient this algorithm is, but I felt like giving this a whirl.
#include <iostream> #include <cmath> using namespace std; bool prime(int x) { bool j = true; for (double i = 2;i == x;i++) { if (x/i == floor(x/i)) { j = false; } } return j; } int main() { cout << prime(4) << endl; return 0; } It returns "1" (true.) Why is this? Obviously, an error on my part. 


#2
Apr412, 03:29 PM

P: 642

This is one of the times I wish I could delete my own threads. I used = instead of ==. Still not working. Edited the original post.



#3
Apr412, 03:32 PM

P: 194




#4
Apr412, 03:39 PM

P: 642

C++ prime testing
I managed to figure the new problem out, I used == when I should've used !=. These =, ==, and != are killing me! :)



#5
Apr412, 04:17 PM

P: 450

You can write it like this if you want.



#6
Apr412, 04:23 PM

P: 642

Now, for fun, I decided to see if I could make a perfect number tester. What's wrong with this function?
EDIT: Figured it out. *bashes head against wall* I started counting factors at 2, not 1. EDIT: And it's still looking for 33550336. 


#7
Apr412, 04:54 PM

P: 450

Integers are exact values while doubles are approximate values. It seams possible that as you add up i's as doubles, you might end up with a loss of precision enough that i != x when you would expect it to and you will get stuck in an infinite loop. I just did a test and found that 2.0000000000000001==2 , but 2.000000000000001 !=2 


#8
Apr412, 05:05 PM

P: 450

I just ran a test and found this out.



#9
Apr412, 05:23 PM

P: 194

a/b == floor(a/b) is ugly to begin with. Those modulus operators don't exist for no reason.



#10
Apr412, 05:43 PM

Engineering
Sci Advisor
HW Helper
Thanks
P: 7,104

... but you shouldn't really be surprised that if x is a 32bit signed integer, it can't hold a number bigger than 2^{31}. On the other hand a double can hold integers up to about 2^{52} exactly, so sometimes storing integer values in doubles wins over storing them in integers. Try the same code with "long x = 2" (if your implementation uses 64bit long integers) to see when that falls over. Actually, it might work beyond 52 iterations, because a double can hold integer powers of 2 exactly right up to the maximum value for a double, which is bigger than 10^{300}. But C++ it won't necessarily print those values accurately to 300 digits precision, of course. 


#11
Apr412, 10:20 PM

P: 737

"long long" is always at least 64 bits wide on any x86 arch, if not 128. Use long long if you need more range, but stay away from floating point numbers.
Use % to check for remainder. For example, if i % p == 0, then p divides i and i isn't prime if p is any number but i or 1. Also, if you need guaranteed width, look at cstdint. 


#12
Apr512, 04:58 AM

P: 194

"64 bits ought to be anything for anyone."  Me. 


#13
Apr612, 05:15 AM

P: 188

When comparing doubles (floating point numbers in general), you should compare to within an error bound to account for small variances in precision.
Example:



#14
Apr612, 09:39 AM

P: 642




Register to reply 
Related Discussions  
Kth Prime Proofs & CoPrime Numbers  Linear & Abstract Algebra  4  
A prime number which equals prime numbers  General Math  10  
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number.  Linear & Abstract Algebra  0  
Prime Numbers in the Diophantine equation q=(n^2+1)/p and p is Prime  Linear & Abstract Algebra  5  
Efficiency: prime test vs prime generator  Linear & Abstract Algebra  14 