Rosetta Code

Carmichael 3 strong pseudoprimes: Difference between revisions

Page Discussion

Carmichael 3 strong pseudoprimes (view source)

Revision as of 05:09, 30 December 2012

1,103 bytes removed ,  11 years ago
Shorter D entry
(→‎{{header|Haskell}}: hlint suggestion: "Redundant bracket")
(Shorter D entry)
Line 27:
 
=={{header|D}}==
From the Python entry, with several changes. Imports the third (extensible) D entry of the Sieve of Eratosthenes Task.
<lang d>import std.stdio, std.algorithm, std.range, std.bitmanip;,
sieve_of_eratosthenes3;
 
/// Extensible sieve of Eratosthenes.
struct IsPrime {
//__gshared static BitArray multiples = [true, true, false];
__gshared static BitArray multiples;
 
static this() {
multiples.length = 3;
multiples[0] = true;
multiples[1] = true;
}
 
static bool opCall(in size_t n) /*nothrow*/ {
if (n >= multiples.length) {
// Extend the sieve.
immutable oldLen = multiples.length; // Not nothrow.
immutable newMax = max((oldLen - 1) * 2, n);
multiples.length = newMax + 1;
foreach (immutable p; 2 .. oldLen)
if (!multiples[p])
for (size_t i = p * ((oldLen + p) / p);
i < newMax + 1; i += p)
multiples[i] = true;
foreach (immutable i; oldLen .. newMax + 1)
if (!multiples[i])
for (size_t j = i * 2; j < newMax + 1; j += i)
multiples[j] = true;
}
return !multiples[n];
}
}
 
 
struct Carmichael {
static struct Tri { int x, y, z; }
immutable int p1;
 
Line 69 ⟶ 39:
}
 
int opApply(immutable int delegate(in ref int[3]Tri) dg) {
int result;
 
Line 83 ⟶ 53:
if (IsPrime(p3))
if ((p2 * p3) % (p1 - 1) == 1) {
// HeapA int[3] literal heap-allocates:.
//int[3]auto triple = [Tri(p1, p2, p3]);
int[3] triple = void;
triple[0] = p1;
triple[1] = p2;
triple[2] = p3;
result = dg(triple);
if (result) break;
Line 99 ⟶ 65:
}
}
 
 
void main() {
Line 105 ⟶ 70:
if (IsPrime(n))
foreach (const c; Carmichael(n))
writefln("%(%d x %)", [c.tupleof]);
}</lang>
{{out}}
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/222673"