Finding Prime Numbers between two inputed values

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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!
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?
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.
Last edited on
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:
1
2
3
4
5
6
7
8
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...
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
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.
Last edited on
@LowestOne: Actually, it's not that bad of a method -- it just takes a bit more memory than the typical
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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...)
Last edited on
Wikipedists wrote:
As a refinement, it is sufficient to mark the numbers in step 3 starting from p2, 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 p2 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
Last edited on
shucks.
Topic archived. No new replies allowed.