C++ help, simple program!

[gnomas]

So my friend and i need help for this program we are writing in C++.
the program should use a function to determine weather a number is prime and then output all prime number from 2 to 10, 000.

the major problem we are having is how to test for a number being prime in a way that you could write it into a program.

any help would be much appreciated! thanks in advance,
Gnomas and co.

[Douglas]

Since you're generating a whole bunch of prime numbers in a list rather than testing one number, google the Sieve of Eratosthenes. For generating a list of all prime numbers below a certain number, given sufficient space to store a true/false for every possible number, it is the most efficient method.

If the goal is to write a function to test for primality and the list is just to test that the function works, then you'll need a different method. To test a number N, first test whether it is even, then test whether any odd number between 3 and the square root of N inclusive divides N evenly. The % operator is especially useful for this. You can try to reduce the number of possible divisors you test, but beyond skipping the multiples of 3 (figure out a way to do this without using division, multiplication or % again, or the effort will be wasted) it is rarely worthwhile unless you are testing for very large primes or generating a list.

[Pyrian]

If you could come up with an efficient way to factorize, you could destroy encryption as we know it. :smallwink:

For a simple brute force method, though, you can just take the remainder (i.e. modulus) (via % operator) of each number by all smaller primes. If all such results are non-zero, then it's prime.

[Douglas]

If you could come up with an efficient way to factorize, you could destroy encryption as we know it. :smallwink:

For a simple brute force method, though, you can just take the remainder (i.e. modulus) (via % operator) of each number by all smaller primes. If all such results are non-zero, then it's prime.
He's only generating primes up to 10000. Efficiency in the sense you mean is not required. Also, he can stop at the square root of the number he's testing.

[Holocron Coder]

In quasi-pseudocode:


int bools[10001];

void init() {
// to start
bools[0] = 0; // not prime
bools[1] = 0; // not prime
bools[2] = 1; // prime

int i;
for (i = 3; i < 10001; i++) {
bools[i] = 1;

int j;
for (j = 0; j < sqrt(i); j++) {
if (bools[j] == 1) {
if (i % bools[j] == 0) {
bools[i] = 0;
break;
}
}
}
}
}

int isPrime(int num) {
return bools[num]; // 1 is prime, 0 is not-prime
}

Actually, that might not quite be pseudocode :smallconfused: And technically gives u primes 0 - 10000.

[Gnomo]

For a simple brute force method, though, you can just take the remainder (i.e. modulus) (via % operator) of each number by all smaller primes. If all such results are non-zero, then it's prime.
This is the simplest and best approach, but take into account that you don't even need to check the values above the squared root of the number, so it's not really that bad.

For example if you want to know if 7659 is a prime number, you check if the numbers up to 87 are not exact divisors of 7659, cause the squared root of that number is 87.515712875.

Why is this? cause beyond the squared root of the number you will only find exact divisors of the number that are already multiples of other divisors of said number.

This should do the trick:


#include <cmath>
#include <iostream>
// cmath is for the sqrt function and iostream is for printf

bool AmIAPrimeNumber(int number)
{
// we don't care about negative values or the stupid 0 =P
if(number < 1)
return false;

// let's check for every k value up to the squared root of number,
// if one of them is a divisor of number then it is not prime =(
for ( int k = 2; k <= sqrt(number); k++ )
if ( number % k == 0 ) return false;

// if we didn't find any divisor of number then it is prime! =)
return true;
}

int main()
{

//now let's print it =D
for (int i = 1; i <= 10000; i++)
{
if ( AmIAPrimeNumber(i) )
{
printf("%i ",i);
}
}

return 0;

}

If this doesn't work... then DIY!

[Mando Knight]

// we don't care about negative values or the stupid 0 =P

But... but... Zero's my hero! (http://tvtropes.org/pmwiki/pmwiki.php/Main/MyHeroZero)

http://upload.wikimedia.org/wikipedia/en/a/a8/Code_Geass_-_Lelouch_of_the_Rebellion_R2_-_06_069_0002.jpg
Care about him. He commands it.



http://images4.wikia.nocookie.net/megaman/images/4/47/Mmxzero.jpg
This guy doesn't really care, though. He's just going to fight for the people he believes in.

[Miklus]

This is the simplest and best approach, but take into account that you don't even need to check the values above the squared root of the number, so it's not really that bad.

For example if you want to know if 7659 is a prime number, you check if the numbers up to 87 are not exact divisors of 7659, cause the squared root of that number is 87.515712875.

Why is this? cause beyond the squared root of the number you will only find exact divisors of the number that are already multiples of other divisors of said number.

This should do the trick:


#include <cmath>
#include <iostream>
// cmath is for the sqrt function and iostream is for printf

bool AmIAPrimeNumber(int number)
{
// we don't care about negative values or the stupid 0 =P
if(number < 1)
return false;

// let's check for every k value up to the squared root of number,
// if one of them is a divisor of number then it is not prime =(
for ( int k = 2; k <= sqrt(number); k++ )
if ( number % k == 0 ) return false;

// if we didn't find any divisor of number then it is prime! =)
return true;
}

int main()
{

//now let's print it =D
for (int i = 1; i <= 10000; i++)
{
if ( AmIAPrimeNumber(i) )
{
printf("%i ",i);
}
}

return 0;

}

If this doesn't work... then DIY!

^What he said! Except that 1 is not a prime number...It will return true for 1, right? Because it skips the loop intirely? And now you have learned where bugs come from, kids!

[scsimodem]

As an engineer, I must state that while 1 is considered a special case and not mathematically a prime number, 1 is, for all practical uses in engineering, a prime number. Therefore, the algorithm stands.

[RS14]

As an engineer, I must state that while 1 is considered a special case and not mathematically a prime number, 1 is, for all practical uses in engineering, a prime number. Therefore, the algorithm stands.

What uses do prime number have in engineering?

It would be best if the program doesn't recognize 1 as a prime. This is the expected behavior.

[Gnomo]

The turning point is in the definition of prime number, during my engineering studies i found 2 different definitions of prime numbers:

1) A prime number is any number that has as its only divisors the numbers 1 and itself.

2) A prime number is any number that has exactly two distinct divisors (yes, 1 and itself).

Definition 1) accepts the number 1 as a prime number, definition 2) doesn't cause both divisors must be different. I think definition 2 is the most accepted one so i guess it's ok not to take number 1 as a prime number.

[RS14]

I went and checked Wikipedia; apparently treating 1 as a prime (http://en.wikipedia.org/wiki/Prime_number#Primality_of_one) is archaic, but not unprecedented.

[Tirian]

1 is not prime. 1 is not prime. 1 is not prime. 1 is not prime.

Mathematicians may have debated this in the past, but they simply don't any longer. There is no benefit in considering 1 to be prime, and virtually every theorem that mentions prime numbers would have to be three words longer if you made that choice. You really need to get on board with this one.

[scsimodem]

1 is not prime. 1 is not prime. 1 is not prime. 1 is not prime.

Mathematicians may have debated this in the past, but they simply don't any longer. There is no benefit in considering 1 to be prime, and virtually every theorem that mentions prime numbers would have to be three words longer if you made that choice. You really need to get on board with this one.

The distinction, however, is irrelevant in engineering, as knowledge of prime numbers is used to see if something can be divided into multiple, equal segments. 1 can't, so that's all that matters. If it means that much to you, an exception can be written into the program, but I just don't think the distinction of 1 as prime or a special case could possibly have any relevance in any program designed for purposes other than serving mathematicians. If it comes into play, an exception can be written, but if it's not needed, writing the exception in just to be correct chews up resources unnecessarily.

For the record, I am a math purist, but when working in practical environments, there's just no rational reason to take the extra time and resources (both of which cost money) to conform to a mathematical truth which has no bearing on the problem itself.

[RS14]

For the record, I am a math purist, but when working in practical environments, there's just no rational reason to take the extra time and resources (both of which cost money) to conform to a mathematical truth which has no bearing on the problem itself.

The program specification calls for it to output a list of primes. The standard meaning of prime does not call for 1 to be included in this list. If the client wishes to use a non-standard definition, even if it is a more useful one, they should have stated that.

Industrial-Grade primes (http://en.wikipedia.org/wiki/Industrial-grade_prime), for example, are in many practical environments just as good as primes, but are probably not desired here.

While in your domain, there may be no reason to not let 1 be a prime, I suspect very strongly that it will matter in e.g. cryptography, which is a highly practical environment.

[Miklus]

As an engineer, I must state that while 1 is considered a special case and not mathematically a prime number, 1 is, for all practical uses in engineering, a prime number. Therefore, the algorithm stands.

As an engineer you know that *I* was tecnically correct and as all we engineers know, that is the BEST KIND of correct! :smallcool:

[Shhalahr Windrider]

For the record, I am a math purist, but when working in practical environments, there's just no rational reason to take the extra time and resources (both of which cost money) to conform to a mathematical truth which has no bearing on the problem itself.
But it takes extra time and resources to write around an algorithm that doesn't behave as expected, even if the it's a more practical version. Then you have to waste the resources to inform and occasionally remind all your programmers, “This algorithm uses a different definition of ‘prime’ than the one you've been using until now.”

Of course, when it comes to programming, there are a number of folks coming to this from a Math stand point, and a number that comes to it from an Engineering standpoint. Perhaps the best compromise is to use a function with a boolean flag (listPrimes(bool includeOne)) with a default set depending on the environment.

[fusilier]

OK, so in the first post he clearly states that the program is supposed to display primes between 2 and 10000!

Second, historically (if you go far enough back), 1 was not a number -- so it couldn't possibly be a prime number. The Euclidian definition of a number was a "multitude of units". Anyway the point is pretty moot, often times there are rather arbitrary decisions, like the factorial of 0.