patterncppModerate
Is this C++ naive primality test done right?
Viewed 0 times
thisnaiveprimalitytestdoneright
Problem
Here's my C++ code:
This function should return true if a number given by value is a prime, and false if a number given by value is a composite. First off, I just want to make sure it works correctly, is fairly efficient (it doesn't have to be the best, but I would like it to be decent for a naive approach), and that the code looks nice.
Thanks!
bool isPrime(double value) {
if (value == 2) // ensure 2 returns true
return true;
else if (value <= 1) // eliminate 1 and all negative numbers
return false;
else if (fmod(value, 2) == 0) // eliminate all even numbers
return false;
for (int i = 3; i < sqrt(value); i++) {
if (fmod(value, i) == 0) {
return false;
}
}
return true;
}This function should return true if a number given by value is a prime, and false if a number given by value is a composite. First off, I just want to make sure it works correctly, is fairly efficient (it doesn't have to be the best, but I would like it to be decent for a naive approach), and that the code looks nice.
Thanks!
Solution
Is there such a thing as a prime real number?
If not then the function signature should use integer (preferably unsigned as there are no negative primes).
Then you should be able to use
Since you have already checked for all even primes:
Here is a link to cool but not obvious optimization (That allows you to avoid checking all multiples of
If not then the function signature should use integer (preferably unsigned as there are no negative primes).
Then you should be able to use
% rather than fmod() which I would suspect is a tad faster but, more importantly, easier to read.Since you have already checked for all even primes:
for (int i = 3; i < sqrt(value); i+=2) {
// ^^^^ No need to increment by 1;
// All evens already checked already so inc by 2
// So just check 3/5/7/9 etcHere is a link to cool but not obvious optimization (That allows you to avoid checking all multiples of
3 as well as 2): https://codereview.stackexchange.com/a/7342/507Code Snippets
for (int i = 3; i < sqrt(value); i+=2) {
// ^^^^ No need to increment by 1;
// All evens already checked already so inc by 2
// So just check 3/5/7/9 etcContext
StackExchange Code Review Q#8667, answer score: 13
Revisions (0)
No revisions yet.