Primality by trial division: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Updated all D entries
Line 564: Line 564:
<lang d>import std.stdio, std.algorithm, std.range, std.math;
<lang d>import std.stdio, std.algorithm, std.range, std.math;


bool isPrime(in int n) pure nothrow {
bool isPrime1(in int n) pure nothrow {
if ((n & 1) == 0 || n <= 1)
if (n == 2)
return n == 2;
return true;
⚫
if (n <= 1 || (n & 1) == 0)
⚫
return false;


for(int i = 3; i <= sqrt(cast(real)n); i += 2)
for(int i = 3; i <= real(n).sqrt; i += 2)
if (n % i == 0)
if (n % i == 0)
return false;
return false;
Line 574: Line 576:
}
}


void main() { // demo code
void main() {
iota(2, 40).filter!isPrime().writeln();
iota(2, 40).filter!isPrime1.writeln;
}</lang>
}</lang>
{{out}}
{{out}}
Line 582: Line 584:
===Version with excluded multiplies of 2 and 3===
===Version with excluded multiplies of 2 and 3===
Same output.
Same output.
⚫
<lang d>bool isPrime2(It)(in It n) pure nothrow {
⚫
<lang d>import std.stdio, std.algorithm, std.range;
⚫
// Adapted from: http://www.devx.com/vb2themax/Tip/19051
// Test 1, 2, 3 and multiples of 2 and 3:
⚫
if (n == 2 || n == 3)
⚫
return true;
else if (n < 2 || n % 2 == 0 || n % 3 == 0)
⚫
return false;


⚫
// We can now avoid to consider multiples of 2 and 3. This
⚫
bool isPrime2(Integer)(in Integer number) pure nothrow {
⚫
// can be done really simply by starting at 5 and
⚫
// Adapted from: http://www.devx.com/vb2themax/Tip/19051
// manually test 1, 2, 3 and multiples of 2 and 3
// incrementing by 2 and 4 alternatively, that is:
⚫
// 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
⚫
if (number == 2 || number == 3)
⚫
// We don't need to go higher than the square root of the n.
⚫
return true;
else if (number < 2 || number % 2 == 0 || number % 3 == 0)
for (It div = 5, inc = 2; div ^^ 2 <= n; div += inc, inc = 6 - inc)
if (n % div == 0)
⚫
return false;
return false;


return true;
⚫
/* we can now avoid to consider multiples
⚫
* of 2 and 3. This can be done really simply
* by starting at 5 and incrementing by 2 and 4
* alternatively, that is:
⚫
* 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
⚫
* we don't need to go higher than the square root of the number */
for (Integer divisor = 5, increment = 2; divisor*divisor <= number;
divisor += increment, increment = 6 - increment)
⚫
if (number % divisor == 0)
⚫
return false;

return true; // if we get here, the number is prime
}
}


void main() { // demo code
void main() {
⚫
import std.stdio, std.algorithm, std.range;
⚫
iota(2, 40).filter!isPrime2().writeln();

⚫
iota(2, 40).filter!isPrime2.writeln;
}</lang>
}</lang>

===Two Way Test===
===Two Way Test===
Odd divisors is generated both from increasing and decreasing sequence, may improve performance for numbers that have large minimum factor.
Odd divisors is generated both from increasing and decreasing sequence, may improve performance for numbers that have large minimum factor.
Line 617: Line 618:
if (n % 2 == 0 || n <= 1)
if (n % 2 == 0 || n <= 1)
return n == 2;
return n == 2;
T head = 3, tail = (cast(T)sqrt(cast(real)n) / 2) * 2 + 1;
T head = 3, tail = (cast(T)real(n).sqrt / 2) * 2 + 1;
for ( ; head <= tail ; head +=2, tail -= 2)
for ( ; head <= tail ; head +=2, tail -= 2)
if ((n % head) == 0 || (n % tail) == 0)
if ((n % head) == 0 || (n % tail) == 0)
Line 624: Line 625:
}
}


void main() { // demo code
void main() {
iota(2, 40).filter!isPrime3().writeln();
iota(2, 40).filter!isPrime3.writeln;
}</lang>
}</lang>


Retrieved from "https://rosettacode.org/wiki/Primality_by_trial_division"