cout prime numbers till 100 using loop

[BGA6444]

The program is supposed to cout prime numbers till 100, however, it just repeatedly outputs 0's. I would greatly appreciate it if someone would help me figure it out. Thanks.

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{

	///int integer;
	int n = 0;
	while (n <= 100)
	{
		
		if ( n/2 == (int)n)
		{
			
			cout << n << " ";
		}
		else 
		{
			n++;
		}
		

	}
	system("PAUSE");
	return 0;
}

[Repeater]

You need to increase n EVERY time round the while loop.

[jonnin]

n/2 == n is never true apart from zero. This is not a prime number finder, nor even close.

the brute force way is to loop again and divide by all the candidate numbers up to the square root of n, looking for a zero remainder (% operation is remainder). There are a few other ways... you can gcd vs 100! (too big to fit in normal integers) or do the sieve algorithm, but for such a small number brute force works.

[BGA6444]

@Repeater I tried that. It didn't give me any number.

@jonnin I don't understand what you mean. What do you mean by divide by all the candidate numbers up to the square root of n, looking for a zero remainder . Could you explain it again to me?

[E0p9LyTq]

I don't understand what you mean

The "brute force" method jonnin described (modified...dividing the number being checked for prime status by two, not taking the square root):

#include <iostream>

bool checkPrimeNumber(int);

int main()
{
   for (int loop = 0; loop <= 100; loop++)
   {
      if (checkPrimeNumber(loop))
      {
         std::cout << loop << ' ';
      }
   }
   std::cout << '\n';
}

bool checkPrimeNumber(int n)
{
   bool flag = true;

   for (int loop = 2; loop <= n / 2; ++loop)
   {
      if (n % loop == 0)
      {
         flag = false;
         break;
      }
   }
   return flag;
}

0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

[jonnin]

brute force programming, in general, means using very simple algorithms that work but do way, way too much work.

Now, basic math.
factors come in pairs. 50*2 = 100: 50 and 2 are a paired set of factors.
if looking for a factor, check n = 1,2,3,4
it should be, but may not be, obvious that as n increases, the other factor decreases:
1 100
2 50
4 25 <- decreases
10, 10 <- now what? 10 is the square root of 100.
11, ???? what number can this possibly be that we have not already tested? Nothing, there is no value for 11*X = 100 where X > 11. If X < 11, we already tested it.

basic math 2: if the remainder of something is zero, it was divided evenly, by definition.
100 %5 = 0. 5 is a factor of 100.
100%6 is not zero. 6 is not a factor of 100. That is what the remainder MEANS.

[icy1]

@BGA6444 Sieve of Eratosthenes is your friend https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes . It's a good exercise to translate various "pseudocode" you may come across into code.

@FurryGuy 0 and 1 are not prime

[Repeater]

if ( n/2 == (int)n)

This is testing that n/2 (i.e. half of n) is equal to n.

Does that seem sensible? This is clearly not a test for prime numbers.

[lastchance]

@jonnin is correct: sufficient to check up to sqrt( n ). If you haven't found a factor by then you aren't going to.

Not sure what compiler optimisation would do, but I wouldn't work out sqrt( n ) every pass through the loop, though.

[E0p9LyTq]

icy1 wrote:

@FurryGuy 0 and 1 are not prime

That is why a brute force prime number checker starting at 0 is a bad idea. Start at 2 and you get the correct prime numbers.

The OP was checking starting at zero, so I duplicated that less than perfect logic.

Sometimes fixing one problem, bad algorithm for determining primes, shows other problems. The second problem is presuming 0 and 1 can be checked for prime status.

Easiest method is do some exclusionary logic in checkPrimeNumber. Rather brutish force still, but it works:

bool checkPrimeNumber(int n)
{
   bool flag = true;

   if (n < 2)
   {
      flag = false;
      return flag;
   }

   for (int loop = 2; loop <= n / 2; ++loop)
   {
      if (n % loop == 0)
      {
         flag = false;
         break;
      }
   }
   return flag;
}

[jonnin]

this will get you the ones > 10, but I am not handling the 2-10 values. Its a wonky way to do it anyway. The trouble with hardcoding the value is that it will pick up 6 if you try to tweak it to get the smaller numbers. If you grow the 210 number as you iterate and find more primes, that issue clears up, but its more code.

for(int i = 2; i < 100; i++)
{
if(__gcd(i,210) == 1)
cout <<i<< " ";
}

210 is 2*3*5*7 (a reduced factorial to the sqrt of the target).
/shrug you can play with the idea if you want. Its intractable for larger targets, but an amusing fun with math approach.

edit:
I also messed up. 9 does not belong in that sequence. OOPS! Fixed!

[lastchance]

For one of the most efficient divisor-check methods @JLBorges gave a rather comprehensive function at
http://www.cplusplus.com/forum/beginner/213292/#msg995584

For numbers much bigger than 100, and to get the whole set of primes up to a bound, @icy's Sieve-Of-Eratosthenes algorithm digs the necessary primes out in one go. (And is highly efficient because it uses just addition rather than lots of divides).

[BGA6444]

Oh okay. Thank you all so much! This all means a lot to me!