Finding Prime Numbers between two inputed values

[hm8]

Hello. I'm trying to write a program where the user inputs two values, and then the program will find all of the prime numbers between the two values, inclusive. The inputs must be between 4 and 1000000.

Here's what I have so far.

int main(void)
{

	int a,b,i,j;

	do
	{	cout << "Enter a number: ";
		cin >> a;
		if (a < 4 || a > 1000000) 
		{	cout << "Input must be between 4 and 1000000 inclusive." << endl;
		}
	}while (a < 4 || a > 1000000);

	do
	{	cout << "Enter a second number: ";
		cin >> b;
		if (b < 4 || b > 1000000) 
		{	cout << "Input must be between 4 and 1000000 inclusive." << endl;
		}
	}while (b < 4 || b > 1000000);

	if (a > b)
	{	int hold;
		hold = b;
		b = a;
		a = hold;
	}

	cout << "The prime numbers between " << a << " and " << b << " inclusive are: " << endl;

	for (i = a; i <= b; i++)
	{	for (j = 2; j < i; j++);
		{	if (!(i%j)&&(i!=j)) cout <<"break"; 
            if (j==i) cout << i << endl;		
		}
	}

return 0;
}

I've gotten it so that it accepts integers a and b, and then switches them if a is larger than b. That part works fine.

I can't seem to get the prime number part to work though. In my head, the program will set i=a. Then, it will go through all values between 2 and i (this is in variable j) . If !(i%j) (i.e. the number doesn't divide perfectly), and i != j, the loop breaks and it goes to the next value of i. If it gets through all the numbers and gets to the point where j is equal to i, it prints that i is a prime number.

However...when I run my program, it just prints out every number between the two inputs (not just the primes).

Any help you could give would be greatly appreciated. Thanks!

[packetpirate]

http://en.wikipedia.org/wiki/Eratosthenes_Sieve

[hm8]

Thanks. However, this is actually for an assignment for school and I think my teacher may be suspicious if I use an algorithm like that... is there a more intuitive way to do it?

[Lowest0ne]

Packetpirate, your method requires making a list of all of the numbers between 2 and n. Since n can be 1 million, I wouldn't recommend allocating (and initializing) that much memory. Not only that, but then you're going to have to flag those numbers somehow. Very heavy.

The fastest I ever got a "find prime" program was one that would build an array of primes using that same array to find the next prime.

Anyway, there is a lot wrong with your code there hm8. Your second for loop has a semi-colon after it, so all that loop does is make j = i. Secondly,

if (!(i%j))

You're saying if the number does divide perfectly. Zero is false in c++ and anything else is true. I would consider not using something like !(i%j), it's just hard to read.

You are also doing a lot of testing for if j = i in a for loop that is set up for j to never equal i. (If you take that semi-colon out).

and finally, you can't just cout "break" to break a loop.

You have the right idea as far as the algorithm to actually figuring out whether a number is prime or not, I would say. I will give one hint though, you don't have to count all the way up to b.

[long double main]

Here's your problem:
for (j = 2; j < i; j++);

The semicolon shouldn't be there. (this is on line 32 in your post)
Also, the next line,
if (j==i) cout << i << endl;
will never happen because the program stops looping when j == i, so that will never get executed.

Oh, and
cout << "break";
won't actually break out of the loop.
You would need:

for (i = a; i <= b; i++)
{
    for (j = 2; j <= i; j++) // Changed the < to <=, and got rid of semicolon
    {
        if (!(i%j)&&(i!=j)) break;
        if (j==i) cout << i << endl;
    }
}

Of course, that's not the best way to check if a number is prime, but I'm just helping you fixe your code...

[Albatross]

LowestOne: I hate to be the person who calls people out on things, but actually, the list need only be made for the integers between 2 and n^0.5 (the square root of n). Sure, a composite number could have larger prime factors than that, but to get the original number they'd need to be multiplied by a smaller factor which would already have been dealt with in a previous iteration of the loop.

-Albatross

[Lowest0ne]

I'm just going from the link:

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1: Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
2: Initially, let p equal 2, the first prime number.
3: Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4: Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

This is a horrible way for a computer to figure out primes, think about it.

[long double main]

@LowestOne: Actually, it's not that bad of a method -- it just takes a bit more memory than the typical

bool isPrime(int num)
{
	if (num % 2 == 0 && num != 2)
		return false;
	
	bool prime = true;
	for (int i = 3; i <= sqrt(static_cast<double>(num)); i += 2)
		if (num % i == 0)
		{
			prime = false;
			break;
		}
	return prime;
}

In fact, I just tested it on my computer (both the function above and the sieve method).
I had the program generate a list of primes under 10 million (the memory to store all 664579 prime numbers in a std::vector allocated before I started the timer) using each of those two methods.

Using that function above, it took nearly a minute to complete.
Using a sieve of Eratosthenes (not the exact method you posted above -- but close), it took less than a quarter second.

(For small numbers, or just testing primality for a few numbers, that function above will do the job. But if you need a list of a bunch of prime numbers, then a prime sieve might be something to consider...)

[Albatross]

Wikipedists wrote:

As a refinement, it is sufficient to mark the numbers in step 3 starting from p², as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p² is greater than n.

It's written just below the bit about the algorithm description. While I admit it should've been in the algorithm description itself... it's there, right? :/

EDIT: Added the superscript back in.

-Albatross

[Lowest0ne]

shucks.