Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import std.algorithm;
- import std.math;
- import std.stdio;
- import std.stream;
- // Adapting Project Euler problem #10 algorithm.
- bool[] generatePrimeSieve(ulong limit)
- in {
- assert (limit >= 1);
- }
- body {
- bool[] primeSieve;
- const ulong crossLimit = cast(ulong)(floor(sqrt(cast(real)limit)) - 1)/2;
- primeSieve.length = limit / 2;
- primeSieve.fill(true);
- primeSieve[0] = false; // special case for one
- foreach (i, ref b; primeSieve[1 .. crossLimit])
- if (b)
- for (auto j = 2*(i+1)*(i+2); j <= (limit - 1)/2; j += 2*(i+1)+1)
- primeSieve[j] = false;
- return primeSieve;
- }
- bool checkPrime(ulong n, bool[] primeSieve)
- {
- if (n == 0 || n == 1)
- return false;
- if (n == 2)
- return true;
- else
- if (n % 2 == 0)
- return false;
- return primeSieve[(n-1)/2];
- }
- void loadPrimeSieve(ref bool[] sieve, string inputFilename)
- {
- auto inputFile = new BufferedFile;
- ulong tempLength;
- inputFile.open(inputFilename);
- inputFile.read(tempLength);
- sieve.length = tempLength; // some rough edges
- inputFile.read(cast(ubyte[])sieve);
- clear(inputFile);
- }
- void savePrimeSieve(bool[] sieve, string outputFilename)
- {
- auto outputFile = new BufferedFile;
- outputFile.create(outputFilename);
- outputFile.write(cast(ulong)sieve.length);
- outputFile.write(cast(ubyte[])sieve);
- outputFile.flush;
- clear(outputFile);
- }
- void main()
- {
- immutable ulong limit = 30_000_000;
- bool[] primeSieve1 = generatePrimeSieve(limit);
- bool[] primeSieve2;
- savePrimeSieve(primeSieve1, "primeSieve.dat");
- loadPrimeSieve(primeSieve2, "primeSieve.dat");
- ulong n;
- write("Enter a positive integer for primality test: ");
- readf("%s\n", &n);
- writeln("Hmm, so is the number ", n, " a prime? ",
- checkPrime(n, primeSieve2) ? "Yes." : "No.");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement