Program to find prime numbers

Question

I want to find the prime number between 0 and a long variable but I am not able to get any output.

The program is

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication16
{
    class Program
    {
        void prime_num(long num)
        {
            bool isPrime = true;
            for (int i = 0; i <= num; i++)
            {
                for (int j = 2; j <= num; j++)
                {
                    if (i != j && i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    Console.WriteLine ( "Prime:" + i );
                }
                isPrime = true;
            }
        }

        static void Main(string[] args)
        {
            Program p = new Program();
            p.prime_num (999999999999999L);
            Console.ReadLine();
        }
    }
}

Can any one help me out and find what is the possible error in the program?

Answer 1

The Sieve of Eratosthenes answer above is not quite correct. As written it will find all the primes between 1 and 1000000. To find all the primes between 1 and num use:

private static IEnumerable Primes01(int num)
{
    return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))
        .Aggregate(Enumerable.Range(1, num).ToList(),
        (result, index) =>
            {
                result.RemoveAll(i => i > result[index] && i%result[index] == 0);
                return result;
            }
        );
}

The seed of the Aggregate should be range 1 to num since this list will contain the final list of primes. The Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) is the number of times the seed is purged.

Answer 2

This is the fastest way to calculate prime numbers in C#.

   void PrimeNumber(long number)
    {
        bool IsprimeNumber = true;
        long  value = Convert.ToInt32(Math.Sqrt(number));
        if (number % 2 == 0)
        {
            IsprimeNumber = false;
        }
        for (long i = 3; i <= value; i=i+2)
        {             
           if (number % i == 0)
            {

               // MessageBox.Show("It is divisible by" + i);
                IsprimeNumber = false;
                break;
            }

        }
        if (IsprimeNumber)
        {
            MessageBox.Show("Yes Prime Number");
        }
        else
        {
            MessageBox.Show("No It is not a Prime NUmber");
        }
    }

Answer 3

Prime Helper very fast calculation

public static class PrimeHelper
{

    public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
    {
        return (new PrimesInt32(maxNumber));
    }

    public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
    {
        return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
    }

    public static bool IsPrime(this Int64 number)
    {
        if (number < 2)
            return false;
        else if (number < 4 )
            return true;

        var limit = (Int32)System.Math.Sqrt(number) + 1;
        var foundPrimes = new PrimesInt32(limit);

        return !foundPrimes.IsDivisible(number);
    }

    public static bool IsPrime(this Int32 number)
    {
        return IsPrime(Convert.ToInt64(number));
    }

    public static bool IsPrime(this Int16 number)
    {
        return IsPrime(Convert.ToInt64(number));
    }

    public static bool IsPrime(this byte number)
    {
        return IsPrime(Convert.ToInt64(number));
    }
}

public class PrimesInt32 : IEnumerable<Int32>
{
    private Int32 limit;
    private BitArray numbers;

    public PrimesInt32(Int32 limit)
    {
        if (limit < 2)
            throw new Exception("Prime numbers not found.");

        startTime = DateTime.Now;
        calculateTime = startTime - startTime;
        this.limit = limit;
        try { findPrimes(); } catch{/*Overflows or Out of Memory*/}

        calculateTime = DateTime.Now - startTime;
    }

    private void findPrimes()
    {
        /*
        The Sieve Algorithm
        http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
        */
        numbers = new BitArray(limit, true);
        for (Int32 i = 2; i < limit; i++)
            if (numbers[i])
                for (Int32 j = i * 2; j < limit; j += i)
                     numbers[j] = false;
    }

    public IEnumerator<Int32> GetEnumerator()
    {
        for (Int32 i = 2; i < 3; i++)
            if (numbers[i])
                yield return i;
        if (limit > 2)
            for (Int32 i = 3; i < limit; i += 2)
                if (numbers[i])
                    yield return i;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    // Extended for Int64
    public bool IsDivisible(Int64 number)
    {
        var sqrt = System.Math.Sqrt(number);
        foreach (var prime in this)
        {
            if (prime > sqrt)
                break;
            if (number % prime == 0)
            {
                DivisibleBy = prime;
                return true;
            }
        }
        return false;
    }

    private static DateTime startTime;
    private static TimeSpan calculateTime;
    public static TimeSpan CalculateTime { get { return calculateTime; } }
    public Int32 DivisibleBy { get; set; }
}

Answer 4

EDIT_ADD: If Will Ness is correct that the question's purpose is just to output a continuous stream of primes for as long as the program is run (pressing Pause/Break to pause and any key to start again) with no serious hope of every getting to that upper limit, then the code should be written with no upper limit argument and a range check of "true" for the first 'i' for loop. On the other hand, if the question wanted to actually print the primes up to a limit, then the following code will do the job much more efficiently using Trial Division only for odd numbers, with the advantage that it doesn't use memory at all (it could also be converted to a continuous loop as per the above):

static void primesttt(ulong top_number) {
  Console.WriteLine("Prime:  2");
  for (var i = 3UL; i <= top_number; i += 2) {
    var isPrime = true;
    for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
      if (i % j == 0)  {
        isPrime = false;
        break;
      }
    }
    if (isPrime) Console.WriteLine("Prime:  {0} ", i);
  }
}

First, the question code produces no output because of that its loop variables are integers and the limit tested is a huge long integer, meaning that it is impossible for the loop to reach the limit producing an inner loop EDITED: whereby the variable 'j' loops back around to negative numbers; when the 'j' variable comes back around to -1, the tested number fails the prime test because all numbers are evenly divisible by -1 END_EDIT. Even if this were corrected, the question code produces very slow output because it gets bound up doing 64-bit divisions of very large quantities of composite numbers (all the even numbers plus the odd composites) by the whole range of numbers up to that top number of ten raised to the sixteenth power for each prime that it can possibly produce. The above code works because it limits the computation to only the odd numbers and only does modulo divisions up to the square root of the current number being tested.

This takes an hour or so to display the primes up to a billion, so one can imagine the amount of time it would take to show all the primes to ten thousand trillion (10 raised to the sixteenth power), especially as the calculation gets slower with increasing range. END_EDIT_ADD

Although the one liner (kind of) answer by @SLaks using Linq works, it isn't really the Sieve of Eratosthenes as it is just an unoptimised version of Trial Division, unoptimised in that it does not eliminate odd primes, doesn't start at the square of the found base prime, and doesn't stop culling for base primes larger than the square root of the top number to sieve. It is also quite slow due to the multiple nested enumeration operations.

It is actually an abuse of the Linq Aggregate method and doesn't effectively use the first of the two Linq Range's generated. It can become an optimized Trial Division with less enumeration overhead as follows:

static IEnumerable<int> primes(uint top_number) {
  var cullbf = Enumerable.Range(2, (int)top_number).ToList();
  for (int i = 0; i < cullbf.Count; i++) {
    var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
    cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
  } return cullbf; }

which runs many times faster than the SLaks answer. However, it is still slow and memory intensive due to the List generation and the multiple enumerations as well as the multiple divide (implied by the modulo) operations.

The following true Sieve of Eratosthenes implementation runs about 30 times faster and takes much less memory as it only uses a one bit representation per number sieved and limits its enumeration to the final iterator sequence output, as well having the optimisations of only treating odd composites, and only culling from the squares of the base primes for base primes up to the square root of the maximum number, as follows:

static IEnumerable<uint> primes(uint top_number) {
  if (top_number < 2u) yield break;
  yield return 2u; if (top_number < 3u) yield break;
  var BFLMT = (top_number - 3u) / 2u;
  var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
  var buf = new BitArray((int)BFLMT + 1,true);
  for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
      var p = 3u + i + i; if (i <= SQRTLMT) {
        for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
          buf[(int)j] = false; } yield return p; } }

The above code calculates all the primes to ten million range in about 77 milliseconds on an Intel i7-2700K (3.5 GHz).

Either of the two static methods can be called and tested with the using statements and with the static Main method as follows:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

static void Main(string[] args) {
  Console.WriteLine("This program generates prime sequences.\r\n");

  var n = 10000000u;

  var elpsd = -DateTime.Now.Ticks;

  var count = 0; var lastp = 0u;
  foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }

  elpsd += DateTime.Now.Ticks;
  Console.WriteLine(
    "{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
    count, n, lastp,elpsd / 10000);

  Console.Write("\r\nPress any key to exit:");
  Console.ReadKey(true);
  Console.WriteLine();
}

which will show the number of primes in the sequence up to the limit, the last prime found, and the time expended in enumerating that far.

EDIT_ADD: However, in order to produce an enumeration of the number of primes less than ten thousand trillion (ten to the sixteenth power) as the question asks, a segmented paged approach using multi-core processing is required but even with C++ and the very highly optimized PrimeSieve, this would require something over 400 hours to just produce the number of primes found, and tens of times that long to enumerate all of them so over a year to do what the question asks. To do it using the un-optimized Trial Division algorithm attempted, it will take super eons and a very very long time even using an optimized Trial Division algorithm as in something like ten to the two millionth power years (that's two million zeros years!!!).

It isn't much wonder that his desktop machine just sat and stalled when he tried it!!!! If he had tried a smaller range such as one million, he still would have found it takes in the range of seconds as implemented.

The solutions I post here won't cut it either as even the last Sieve of Eratosthenes one will require about 640 Terabytes of memory for that range.

That is why only a page segmented approach such as that of PrimeSieve can handle this sort of problem for the range as specified at all, and even that requires a very long time, as in weeks to years unless one has access to a super computer with hundreds of thousands of cores. END_EDIT_ADD

Answer 5

You can do this faster using a nearly optimal trial division sieve in one (long) line like this:

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);

The approximation formula for number of primes used here is π(x) < 1.26 x / ln(x). We only need to test by primes not greater than x = sqrt(num).

Note that the sieve of Eratosthenes has much better run time complexity than trial division (should run much faster for bigger num values, when properly implemented).

Answer 6

First step: write an extension method to find out if an input is prime

public static bool isPrime(this int number ) {

    for (int i = 2; i < number; i++) { 
        if (number % i == 0) { 
            return false; 
        } 
    }

    return true;   
}

2 step: write the method that will print all prime numbers that are between 0 and the number input

public static void getAllPrimes(int number)
{
    for (int i = 0; i < number; i++)
    {
        if (i.isPrime()) Console.WriteLine(i);
    }
}