Primality by trial division: Difference between revisions
→{{header|Ada}}: added C++
(Clarified task; added Haskell example) |
(→{{header|Ada}}: added C++) |
||
Line 24:
return Result;
end Is_Prime;
=={{header|C++}}==
bool is_prime(unsigned number)
{
// directly check for small numbers
if (number < 11)
{
switch(number)
{
case 2: case 3: case 5: case 7:
return true;
default:
return false;
}
}
else
{
// quickly check for most common cases
switch (number % 30)
{
default:
return false;
case 1: case 7: case 11: case 13: case 17: case 19: case 23: case 29:
// OK, we might have a prime.
// We already have caught all multiples of 2, 3 and 5, so we can start testing at 7.
// We would only have to check for primes, but first checking each numer if it's a prime
// would be too expensive. But we can easily exclude multiples of 2, 3 and 5.
// the array diff contains the steps to go forward (starting from 7; so the first step is
// 4, to go from 7 to 11). The steps are periodic; when we get to the end of the array,
// we have to continue at the beginning
unsigned diff[8] = { 4, 2, 4, 2, 4, 6, 2, 6 };
for(unsigned den=7, pos = 0; den*den <= number; den += diff[pos], pos = (pos+1) % 8)
{
// if we can divide without remainder, it's not a prime
if (number % den == 0)
return false;
}
// if we get here, we have a prime
return true;
}
}
}
=={{header|BASIC}}==
| |||