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).
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.
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:
1 2 3
for(start at two and go until i is not less than num)
if(num is divisable by i)
returntrue;
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.
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:
1 2 3 4 5 6 7
if (myFunc() == SUCCESS)
{
// Do stuff
return someValue;
}
elsereturn ERROR;
Perfectly fine, until you decide you'd like an error message to be displayed:
1 2 3 4 5 6 7 8
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.
int* sieve(int n, int *s = 0)
{
bool *m = newbool[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 = newint[*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:
1 2 3 4 5 6 7 8
int size, *primes = sieve(100, &size);
for (int i = 0; i < size; i++)
{
std::cout << primes[i] << ' ';
}
delete [] primes;