Prime Numbers

[andres serrato capote]

Hi guys, I developed a program that tells you if the number you introduced by keyboard is prime. The code runs nice but the devil (my teacher) told me that was inefficient. And I don't know how to improve it

bool PrimeVLP (int Num)
{
bool prime;
int i, count;
count = 0;

for (i = Num ; i > 0 ; i--)
{
if (Num % i == 0)
{
count++;
}
}

if (count == 2 || Num == 1)
{
prime = 1;
}
else
{
prime = 0;
}

return (prime);
}

[helios]

1 is not prime.

It's enough to test all integers in [1;sqrt(n)] to know if n is prime.

[Duthomhas]

Did your teacher tell you he would be grading based upon how efficient the algorithm is?

I would award you full points*; your algorithm uses the prime number definition in an interesting way.

However, your professor may be interested in seeing a different algorithm: one that does less work. It is sufficient to show that of all whole numbers small enough to (potentially) divide into the given number, not one does.

Hence, you only need to test the whole numbers in the range ( 1, √n ] to see if 'n' is prime (or if it is not evenly divisible by any of those numbers).

Hope this helps.

* for the algorithm. As helios noted, you fail if Num is 1 or less.

[codekiddy]

hi, this may help you:

prime numbers are the numbers than just can be divided between themselves and one (1).
example:
2,3,5,7,11,13,17,19,23
4 is not a prime number because is the result of 2*2
6 is not a prime number bacause is the result of 3*2
8 is not a prime number bacause is the result of 2*2*2
9 is not a prime number bacause is the result of 3*3
10 is not a prime number bacause is the result of 5*2
12 is not a prime number bacause is the result of 2*3*2
14 is not a prime number bacause is the result of 7*2

c/p from google search.

[Duthomhas]

The OP has already demonstrated that he knows that, and his algorithm works (except for the value one, which it incorrectly identifies as prime).

[ne555]

Actually, you only need to test the prime numbers in range ( 1, √n ]

[andywestken]

Your teachers comment about efficiency is, as others have said, is very probably because you're not testing just the range [2, √n]. You don't need to waste time with 1: all ints are divisible by it.

As helios said, 1 is not a primes. This web page provides some info about this:
http://primes.utm.edu/notes/faq/one.html

But you could also test only odd numbers. If it's divible by eny even number, it's already divisible by 2, so you're wasting your time testing an odd number with all the even ones.

even -> is not prime
odd -> try with 3, 5, 7, ... up to sqrt of number

Andy

PS But it's highly unlikely to be because you're not using the AKS primality test (discovered 2002)
http://en.wikipedia.org/wiki/AKS_primality_test
http://fatphil.org/maths/AKS/
http://yves.gallot.pagesperso-orange.fr/src/aks.html <= C++ implementation