Goal: Generate a file of prime numbers

Difficulty: Medium

Prerequisites: Visual Studios or other C# Compiler

As many people are aware, prime numbers are one of the hardest things to find. There really are no really great ways to find large primes. This makes prime numbers perfect for security encryption. One of the most popular types of cryptography that is used widely around the world is the RSA Algorithm (though I believe this uses relative primes). 

There are also several different approaches/algorithms for finding primes. My approach listed below uses a method that incorperates "Trial Division". This means that I check to see if it is divisible by any previously found prime. This is not quite as efficient as the sieve methods, which is where you start with a large bucket of numbers and then eliminate the ones that don't belong. However, the advantage that I have found to using this is that I can stop anywhere in the process and easily pick back up without having to have any special knowledge of where I was, just need the list of primes I had already found, which I take advantage of by writing the prime numbers to a text file.

Notes about the program: This program can become very memory intensive and may need to be run in x64 mode in order to find larger primes, to run in x86 mode please lower the arraySize variable to a suitable size. This program is built to use a single thread and will likely use 100% of 1 CPU core whenever it is running as it is a CPU bound process. This program was written as a Console Application in C# using Visual Studios 2010 and tested using the .NET3.0 framework.

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Find_Primes
{
    class Program
    {
        static void Main(string[] args)
        {
            // Code taken from www.exchangecore.com written by Joe
            /*
             * This script can be stopped and restarted from where it left off
             * assuming that the text file containing a list of prime numbers
             * exists in a {prime}\r\n format
             * 
             * arraySize^2 is the number of primes that will be found
             * setting arraySize to large will exhaust committed memory 
             * and cause out of memory exceptions
             */
            int arraySize = 40960;
            double primesFoundLimit = Math.Pow(arraySize, 2); 
            ulong[][] primes = new ulong[arraySize][];
            for (int i = 0; i < arraySize; i++)
                primes[i] = new ulong[arraySize];
            primes[0][0] = 2;
            ulong number = 3;
            int primesFound = 1;
            if (File.Exists("./primes.txt"))
            {
                using (StreamReader sr = new StreamReader("./primes.txt"))
                {
                    string line;
                    while ((line = sr.ReadLine()) != null)
                        primes[primesFound / arraySize][primesFound++ % arraySize] = ulong.Parse(line);
                }
                number = primes[primesFound / arraySize - 1][(primesFound - 1) % arraySize] + 2;
            }
            else
            {
                using (StreamWriter sw = new StreamWriter("./primes.txt", true))
                {
                    sw.WriteLine("2");
                }
            }

            for (; number < ulong.MaxValue && primesFound < primesFoundLimit; number += 2)
            {
                bool isPrime = true;
                double sqrt = Math.Sqrt(number);
                for(uint primeCount = 0; primeCount < primesFound && primes[primeCount / arraySize][primeCount % arraySize] <= sqrt ; primeCount++)
                {
                    if (number % primes[primeCount / arraySize][primeCount % arraySize] == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if(isPrime)
                {
                    using (StreamWriter sw = new StreamWriter("./primes.txt", true))
                    {
                        sw.WriteLine(number);
                    }
                    primes[primesFound / arraySize][primesFound++ % arraySize] = number;
                }
            }
        }
    }
}

Attached are all the prime numbers up to one hundred million with each number seperated by a carriage return linefeed. (Each number on a new line) - Primes.zip

Comments

Leave a Reply



(Your email will not be publicly displayed.)



Search