How to fix this prime counting algorithm so it can handle larger integers

[galiwocky]

Possibly large long ints

The goal is to count the number of prime numbers in between two integers. At first I used a self-made algorithm which worked perfectly for small integers (int data type). But then the programming judge had a "Runtime Error" verdict. Turns out that it required the program to handle larger integers, possibly of data type long.

EDIT(6/23/2012)

So I used a popular algorithm, the Sieve of Erastothenes which they said can process faster and handle larger integers.

The program assumes that the 1st integer is the lower bound and the 2nd is the upper bound.

Here's the code:

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

long long sieveOfErastothenes(long long lower, long long N) {
	int counter = 0;
	bool isPrime[N + 1];
		
	for (long long i = 2; i <= N; i++)
		isPrime[i] = true;

	for (long long i = 2; i*i <= N; i++) 
	{
		if (isPrime[i]) 
		{
			for (long long j = i; i*j <= N; j++)
				isPrime[i*j] = false;
		}
	}
	for (long long i = lower; i <= N; i++)
	{
		if (isPrime[i])
			counter++;
    }
	 
	return counter;
}

int main()
{
	long long lower, upper;
	int ctr;
	while (cin >> lower >> upper)
	{
		ctr = 0;
		if (lower <= upper)
		{
			ctr = sieveOfErastothenes(lower, upper);
		}
		
		cout << ctr << endl;
	}
	return 0;
}

The input I tested are the following:

2 5
7 8
2 100
100 2
2 3571
2 8
2 300
0 2050000
1000000 3000000

And this is the corresponding input:

3
1
25
0
500
4
62
152382

If you notice, the last line of input 1000000 3000000 was not processed anymore and a window indicated Prime.exe has stopped working. A problem caused the program to stop working correctly.


How will I make the code handle larger inputs? What will I modify to get correct results even for long integers?

[eklavya sharma 2]

I don't think it is possible to handle such large inputs with int as a data type. int is of 4 bytes. So its range is 2147483648, which is less than 3000000000. Long is as big as int, so using int is of no use (atleast this is what sizeof() on my computer says). If your program is working fine with smaller inputs, be calm.

Maybe your computer can't assign that much of memory for the array you are making. Mine can only assign 250000 ints. If you want to use larger numbers and you have Visual C++, you can use __int64. It is 8 bytes long.

Its not just space you need to take care of. Spped is also a concern.

My computer has a 3 Ghz intel i5 processor and 4 GB RAM. I too made a prime number utility once. It statically assigns memory (at the beginning of the program). In that memory, I store prime numbers. Whenever the computer needs prime numbers, it updates the array with new prime numbers.

For eg. I entered lower limit 2 and upper limit 1000000. It took 33.232 seconds to give the answer as 78498. But when I entered the same limits again, it took only 0.014 seconds as it generated prime numbers upto 1000000 during the 1st operation and the second time it only counted the number of primes in the limits (using a binary search-like algorithm). So, you can expect very large limits to take a lots and lots of time (maybe hours)

For the input (100,2) you are getting 0 as the program takes lower limit as 100. To prevent this, check if the 1st argument is larger than the 2nd and swap them if this is true.

These are the values I get for the experiment:

3
1
25
25
500
4
62

If you need to verify in the future the number of primes between 2 numbers, use www.wolframalpha.com. In the text box, enter what you want to find out.

I might be able to find the bug in your program if I look very closely, but that will take a lot of time as I haven't written this code. You can find the bug yourself if you use the debugger and the watch windows. If you use Visual C++, I can help you. The debugger is a tool which lets you execute your program step by step, so you can see what's going on. Watch windows let you see the value of variables. But beware, use it as a last resort or you will get addicted and wouldn't be able to code without.

Most of your outputs are one more than my outputs. But the word 'most' introduces a problem as now you can't just subtract 1 from the answer!

[ResidentBiscuit]

unsigned long long will be able to hold that just fine.

[Torin]

unsigned long long's upper limit is 18,446,744,073,709,551,615, so you'll be fine using that.

[galiwocky]

Thanks for the suggestions. I edited the topic description. I used a new algorithm and it now prints better results. But still, it can't handle long ints, even if I already tried unsigned long long or long long. What to do?

[eklavya sharma 2]

What do you mean by it can't handle large ints? When you enter a large upper limit, what happens? Does your program give a message like "this program has encountered an error and needs to close", does it stop doing anything or does it give a wrong answer?

If your program is giving a wrong answer, then it means that there is a logical error in your program. Tell us the wrong outputs you are getting and we might be able to predict what the problem.

If your program stops doing anything, then it is either going in an infinite loop or it is taking so much time that you don't know that waiting for a long time will give you an answer (latter happened with me once, waited for an hour).

If your program is giving the error message and closing, then this is a runtime error, like allocating a very large array or going out of bounds.

I tried compiling your code. It gave a syntax error at line 9 as N is not constant. Use new to allocate memory.

The size of the array prime[N+1] is N+1 bytes. My computer can allocate about 1,931,082,000 bytes, which is less than the max size of unsigned int, 4,294,967,295. Also the data type which new accepts is unsigned int. If you pass a long long as an argument (in your case N+1) and it is more than the max size of unsigned int, it will be truncated. Hence your program will not work for very large numbers if you use 'Sieve of Eratothenes' algorithm.

Try using some other method. If you don't want memory to be a hurdle, don't allocate any memory. If you want speed, you can only store prime numbers instead of storing a boolean array stating whether eah nummber is prime or not.

[galiwocky]

What do you mean by it can't handle large ints? When you enter a large upper limit, what happens? Does your program give a message like "this program has encountered an error and needs to close", does it stop doing anything or does it give a wrong answer?

Sir, by large ints I mean integers greater than 2 million.

I tried this input

2 5
7 8
2 100
100 2
2 3571
2 8
2 300
0 2050000
1000000 3000000

And the output is

3
1
25
0
500
4
62
152382

If you notice, the last line was not processed and consequently a window appeared with this message

3
1
25
0
500
4
62
152382

The answers printed are actually correct. The only problem is that it cannot process large integers from greater than 3 million. How do I fix it without completely doing away with the method?

[ResidentBiscuit]

Well, considering an int is 4 bytes, with the max of 2.1 billion, I don't think you're issue is a number too large.

A long long, such as you are using, has a maximum of 9,223,372,036,854,775,807, which is well over your 3 million.

[eklavya sharma 2]

I want to point out that you are not deleting memory after allocating it. This is causing a memory leak. This isn't a problem if you are allocating small patches of memory and doing it for a few times. But the computer can run out of memory if you allocate too much memory or allocate memory a large no. of times. If the computer runs out of memory, and then you ask it for memory using new, an exception will be thrown, which will result in an error message. I'm not sure if this the main problem in your program, but using delete can atleast make it faster.