need some hints for homework

[Maxchen]

Homework:
Write a program that finds all of the prime numbers between 1 and 100.

I was trying to get my head around the part: prime numbers. However, I am not sure how to get them work in programming.

Any idea or hints about it?

[4Gb4jE8b]

Remember to think about what a prime number is actually defined as. Other than that I'll point you to the arithmetic operator here: http://www.cplusplus.com/doc/tutorial/operators/

[Chervil]

Well, there are two common approaches to Prime numbers. If you need to find a large number of primes, say 10000 or more then you might use Erastothenes sieve - google it. But in this case, I think it would be simpler to loop through the numbers from 1 to 100 and test each one to see whether it is prime.

How to test whether a number is prime.

I'd recommend this is made into a self-contained function which takes an integer as a parameter, and returns a bool result.
The number 1 by definition is not prime.
Divide the number by each integer starting with 2 and smaller than itself. If the remainder is non-zero in every case then the number is prime. (there are ways to make this process more efficient).

[TheGrayWolf]

+1 for "separate" primality check. As for the more efficient way, that would probably be the check up to the square root of the number.

[Maxchen]

Chervil, would you like to give me bit more hints about the ways to make the process?

[Codeez]

Divide the number by each integer starting with 2 and smaller than itself. If the remainder is non-zero in every case then the number is prime.

Anymore hints he'd be writing it. This quote is all you need. For the actual algorithm you could simply use a for loop and an if statement with modulo in the condition.

For a bit of optimization you could also check first if it's even, 1, or 0 - which wouldn't be prime- and return the bool there and then.

[Superdude]

Here is some pseudo code based on Chervil's idea:

bool isPrime(int num)
{
	for(start at two and go until i is not less than num)
	{
		if(num is divisable by i)
		{
			return false;
		}
	}
	return true;
}

[Codeez]

I think you mean for those true / false statements to be the other way round?

[Superdude]

Oh yeah, my mistake. Should I edit?

[Codeez]

Sure. I'll edit my comment too so he doesn't get doubly confused. :-)

Just a tip (unless you were just doing it to be clearer for him); if you're only executing 1 statement, you can drop the curlies, even for an if in a for. This is equal:

    for(start at two and go until i is not less than num)
	if(num is divisable by i)
	    return true;

[Superdude]

Yeah. That was for clarity. Plus, I think it looks neater just to use it that way always.

[Chervil]

Chervil, would you like to give me bit more hints about the ways to make the process?

I think you need to try to write some code yourself, even if it's only a partial, incomplete version. Then share your code here and we can see where it is you are getting stuck.

[MikeyBoy]

Just a tip (unless you were just doing it to be clearer for him); if you're only executing 1 statement, you can drop the curlies, even for an if in a for.

You can, but I'd strongly recommend against doing that. It's a very easy way to introduce bugs. I've seen it happen many, many times - someone leaves the braces out, because the block only has one line. Then, later, they (or someone else) decide the block needs more lines in it, and adds the line, forgetting to add the braces that are now needed.

Consider:

if (myFunc() == SUCCESS)
{
  // Do stuff
  return someValue;
}
else
  return ERROR;

Perfectly fine, until you decide you'd like an error message to be displayed:

if (myFunc() == SUCCESS)
{
  // Do stuff
  return someValue;
}
else
  std::cout << "MyFunc returned an error" << std::endl;
  return ERROR;

You may laugh, and say nobody would ever make that mistake, but I've seen it happen so many times.

Part of the skill of being a good programmer is adopting practices which make it less likely that bugs will be introduced into your code during further development. This is one such practice.

[Superdude]

Even I have made that mistake before.

[Codeez]

@MikeyBoy You're completely right. I will adopt that practice now.

[Manga]

Make it a habbit boys. Add those braces, it will just pay off in the long run.

[Josue Molina]

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

I love the sieve of Eratosthenes. Here is a quick implementation of it:

int* sieve(int n, int *s = 0)
{
    bool *m = new bool[n + 1]();

    for (int i = 2; i <= n; i++)
    {
        m[i] = true;
    }

    for (int i = 2; i <= n; i++)
    {
        if (!m[i])
        {
            continue;
        }

        for (int j = 2 * i; j <= n; j += i)
        {
            m[j] = false;
        }
    }
    
    for (int i = 0; i < n + 1; i++)
    {
        if (m[i])
        {
            (*s)++;
        }
    }

    int *p = new int[*s], d = 0;

    for (int i = 0; i < n + 1; i++)
    {
        if (m[i])
        {
            p[d++] = i;
        }
    }

    delete [] m;

    return p;
}

This is how it is used:

int size, *primes = sieve(100, &size);

for (int i = 0; i < size; i++)
{
    std::cout << primes[i] << ' ';
}

delete [] primes;

Here is the output:

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

[Manga]

I see the use of 'new' through out your code, but never delete. I thought you should always have a delete go after new for clean up.

Did I miss something?

[Josue Molina]

The program is now more "complete."