0

I have made a small c++ program to check for prime numbers. It seems to work pretty well, but after a while it stops when it gets to 16777213. Can anyone tell me why? Here is my program: 

#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        float div = n/float(i);
        if (!(div-floorf(div))) return false;
    }
    return true;
};

int main() {
    for(int a = 1; a < 18446744073709551614; a++ )
        if (isPrime(a))
            cout << a << endl;
    return 0;
}
  • 2
    `a` is an `int`, and you are looping it till a whooping `18446744073709551614`? – abhishek_naik May 23 '16 at 05:28
  • a) No normal signed int type in todays devices and C++ standard can store that number. b) Don't you know how long loop this will take? c) Someone upvoted this brute-force prime search for 2^64 numbers? :( – deviantfan May 23 '16 at 05:33
  • 2
    @deviantfan upvoting doesn't mean you like the question. It means the question follows the guidelines. – xaxxon May 23 '16 at 05:38
  • @xaxxon ...of course everyone is free to vote. I for my part can't upvote this. Brett, you have about 5*10^28 divisions and floorf's ... such a program won't finish while you're alive. – deviantfan May 23 '16 at 05:43
  • @LokiAstari - wrong, see http://en.cppreference.com/w/cpp/language/integer_literal . If a number literal does not fit into int, if will be long int or long long int. – user31264 May 23 '16 at 05:48
  • @user31264 Wrong again. Read the "no suffix, decimal base" box carefully: there is no unsigned. – deviantfan May 23 '16 at 05:52
  • @deviantfan I know it will never reach this number, and I don't expect it to. I had lower numbers in there, and I purposely changed it to something it can never reach just to see if it ever slowed down. I should probably take that out altogether now that I am not limiting it. –  May 23 '16 at 05:57
  • @deviantfan, read my comment again. There is no word "unsigned" in my comment. – user31264 May 23 '16 at 05:58
  • @xaxxon I don't expect it to finish, I just had that in there because I never wanted it to stop, I wanted to see if it ever slowed down. I am not trying to make an efficient program, this was just a small project as I am trying to learn c++. –  May 23 '16 at 06:01
  • @user31264 Exactly. But this number (18...) can't fit in a signed type, and that's all you get without suffix in decimal base. – deviantfan May 23 '16 at 06:01
  • Just some things to make run better, switch for loop to a while loop so it stops once it finds a divisor. Use a simple congruence mod operation `%` instead of floor to return the remainder, have exit while loop if remainder is 0 cause it isn't prime. Even still you can increment by 2 at least, obviously even numbers aren't prime. If it has a factor which is even, guess what the number in question is and isn't. You can use a file or some storage device to store the numbers which are prime, and only loop through the found primes instead of just odd numbers. – marshal craft May 23 '16 at 06:49

1 Answers1

4

Your program stops printing primes because floorf returns a 24-bit precise value. So for any prime [or non-prime] number above 224 the calculation div - floorf(div) will return a zero value [because the mantissa value is always "the same" for both values - there is no space for a fraction part in the mantissa] -> your function returns false as to whether the number is prime or not.

Even if you move to double, you'll get the same problem, just further along.

Use integer math, and use the % operator to determine if it divides evenly or not.

As comments mention, you have a few other issues with your code. Do fix those too...

Edit: To clarify, your program continues to TRY to calculate prime numbers. It just finds all of them to be "not prime" because of the lack of precision in float, resuling in "no difference", once you get to the limit of precision.

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
  • While I agree with you, I think this is not his question. In my opinion, the OP wants to know *why his program stops when it gets to 16777213*. And I think that is because he has used a very large number `18446744073709551614`. – abhishek_naik May 23 '16 at 05:44
  • 1
    224 is 16777216, so 16777213 happens to be the prime number just before that. Since ALL numbers above that will result in zero in the subtraction, the function will return false for EVERY number above that. Change the number to 35000000, and it will make zero difference to the outcome of the posted code. It has EVERYTHING to do with how floating point numbers work, and is not, as such, UB [for that part of the code, and thus that actual number being the "last output"]. – Mats Petersson May 23 '16 at 06:09