C++

Forum

 
Largest prime number program

mefelsen (2)
I am supposed to create a program where you enter a number and the program tells you the largest prime number less than the one you entered.

It works some of the time and I am not sure what is wrong with it. This is for a programming class and I am not allowed to use functions, only loops so this is what I am working with

int main()
{
bool isPrime = false;
int num = 0;
int primenum = 0;
int ans = 0;

cout << "Input an integer: ";
cin >> num;

while(primenum < num)
{
for(int i = 2; i <= num/2; i++)
{
if(primenum%i == 0)
{
isPrime = false;
}
else if(primenum%i != 0)
{
isPrime = true;
}
}
if(isPrime)
{
ans = primenum;
}
primenum++;
}



cout << ans << " is the largest prime <= " << num << endl;

return (0);
}
Ganado (6812)
Please edit your post and put [code] [/code] tags between your code.

Do you indent your code? Because once you correctly indent your code, the problem becomes at least bit more apparent.

This is the meat of your prime logic:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
		for (int i = 2; i <= num/2; i++)
		{
			if (primenum%i == 0)
			{
				isPrime = false;
			}
			else if (primenum%i != 0)
			{
				isPrime = true;
			}
		}
		if (isPrime)
		{
			ans = primenum;
		}


I think it's absolutely ridiculous that you're not allowed to make a function like int isPrime(int num), but anyway...

The problem is you are treating checking whether a number is a prime with the same weight as checking something isn't a prime.
This part of your code is wrong:
1
2
3
4
 
			else if (primenum%i != 0)
			{
				isPrime = true;
			}

because a number not being divisible by one particular number is not a sufficient test to prove that a number is prime. it must not be divisible by every number between itself and 1 (with further optimizations being done from there).

In other words: You're not checking if a number is prime, you're only checking if the last factor before num/2 is prime.

So: Assume that a number isPrime from the start. Then, when you find a divisible factor, you say it isn't prime

1
2
3
4
5
6
7
8
 
			if (primenum%i == 0)
			{
				isPrime = false;
			}
			else if (primenum%i != 0)
			{
				isPrime = true;
			}


Edit: You also need to reset isPrime to true before the inner for loop.

PS: Although in this particular example, the logic is wrong either way, it's important to note the redundancy in what you wrote.
1
2
3
4
5
6
7
8
 
if (my_var == 0)
{
	/// do something
}
else if (my_var != 0)
{
	/// do something else
}

The second if is redundant because if my_var == 0 is false, that already implies that my_var != 0.
You can simply do
1
2
3
4
5
6
7
8
 
if (my_var == 0)
{

}
else
{

}



(@lastchance below: That's definitely the more efficient solution, although what he already has was almost correct, so I just kept most of his existing logic intact.)
Last edited on
lastchance (6980)
Topic archived. No new replies allowed.