Listing primes using list comprehensions with the aid of PLINQ in C#

ddanbe 0 Tallied Votes 411 Views Share

OH noo, please not that again! Yeah, primes sigh. But they play a minor role here as a perfect victim to explain some other things. Would not advise to use the algorithm here to calculate them in real life. There are languages like Python, F#, Haskell etc. who have list comprehension on board. I was wondering how to do it in C#. Looked up some examples on the net and concoct my own here. See the factors method on line 84 and the primes method on line 109. What I like about this code is that it is so concise yet easy to comprehend.( That is I think it is :) )
PLINQ joins in as I use the AsParallel() extension on line 111. You might as well add the AsOrdered() extension. Parallel processors don't always deliver their tasks in order! Working parallel is not always advisable. Think of numbers less than 1000 or so. Calculate primes from 2 to 100000 and you're in business. Calculating all the primes up to 1234567 on my i7 four core machine in parallel, still takes about half an hour, while taking up 96% of total processor time(seen in Task Manager). Leave .AsParallel().AsOrdered()out if you want to see the time difference. Enjoy. Any comments are always welcome.

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

namespace PrimeLister
{
    /// <summary>
    /// Visual Studio Community 2017
    /// 
    /// Listing primes using list comprehensions with the aid of PLINQ
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            int cNumber = InputInteger();

            Console.WriteLine("The number {0} has following factors:", cNumber);
            List<int> facs = factors(cNumber);
            PrintOut(facs);

            if (prime(cNumber))
                Console.WriteLine("It is a prime number");
            else
                Console.WriteLine("It is not a prime number");

            Console.WriteLine("The primes up to this number are:");
            var STW = Stopwatch.StartNew();                
                List <int> prims = primes(cNumber); 
            STW.Stop();
            PrintOut(prims);

            Console.WriteLine("Total number of primes up to {0} is: {1}", cNumber, prims.Count());
            Console.WriteLine("Total time calculating: {0}", STW.Elapsed.ToString(@"mm\:ss\.fff"));

            Console.ReadKey();
        }

        /// <summary>
        /// Some way where it is only possible to input numbers
        /// </summary>
        /// <returns>on success, the inputted number</returns>
        static int InputInteger()
        {
            string intStr;
            int numb;
            do
            {
                Console.Write("Input an integer: ");
                intStr = string.Empty;
                intStr = Console.ReadLine();
            } while (!Int32.TryParse(intStr, out numb));
            return numb;
        }

        /// <summary>
        /// Print out a formatted list of integers on the console
        /// </summary>
        /// <param name="aList">here a list of integers</param>
        static void PrintOut(List<int> aList)
        {
            const int cNumbersOnaLine = 15;

            int Counter = 0;
            foreach (var result in aList)
            {
                Console.Write("{0,6} ", result);
                Counter++;
                if (Counter > cNumbersOnaLine)
                {
                    Counter = 0;
                    Console.WriteLine();
                }
            }
            Console.WriteLine();
        }

        /// <summary>
        /// Get a list of factors from a number
        /// </summary>
        /// <param name="number">The number to handle</param>
        /// <returns>The list of factors</returns>
        static List<int> factors(int number)
        {
            return new List<int>(from x in Enumerable.Range(1, number)
                                 where number % x == 0
                                 select x);
        }

        /// <summary>
        /// Test if a number is prime
        /// </summary>
        /// <param name="number"></param>
        /// <returns>true or false</returns>
        static bool prime(int number)
        {
            //return factors(number).Count() == 2; or
            return factors(number).SequenceEqual(new List<int>() { 1, number });
        }

        /// <summary>
        /// Get a list of primes up to a certain number.
        /// Leaving AsParallel out it's 4 times slower on my system
        /// but depending on how may numbers you choose!
        /// </summary>
        /// <param name="upto">the maximum</param>
        /// <returns>A list of primes in the range 2 until upto</returns>
        static List<int> primes(int upto)
        {
            return new List<int>(from x in Enumerable.Range(2, upto).AsParallel().AsOrdered()
                                 where prime(x)
                                 select x);
        }
    }
}

Dani AI

Generated

Nice, compact PLINQ demo from and a good prompt for discussion. Two concrete things worth noting that will immediately improve correctness and speed: (1) an off‑by‑one in the range generation, and (2) the per‑number factorization approach is very expensive compared with a small optimized primality test or a sieve.

Enumerable.Range(start, count) takes a count, not an end value — so Enumerable.Range(2, upto) yields 2..(upto+1). Use the count Math.Max(0, upto - 1) when the intent is 2..upto. Also avoid building full factor lists for each number; a tighter primality test is much cheaper:

static bool IsPrime(int n)
{
    if (n < 2) return false;
    if (n == 2) return true;
    if ((n & 1) == 0) return false;
    int r = (int)Math.Sqrt(n);
    for (int i = 3; i <= r; i += 2)
        if (n % i == 0) return false;
    return true;
}

If the goal is "all primes up to N", the Sieve of Eratosthenes is the right tool: O(N log log N) and far faster than checking each number. Use a bool[] or BitArray to mark composites, then collect indices that remain true:

static List<int> Sieve(int n)
{
    var isPrime = new System.Collections.BitArray(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    int limit = (int)Math.Sqrt(n);
    for (int i = 2; i <= limit; i++)
        if (isPrime[i])
            for (int j = i * i; j <= n; j += i)
                isPrime[j] = false;
    var primes = new List<int>();
    for (int i = 2; i <= n; i++) if (isPrime[i]) primes.Add(i);
    return primes;
}

A few practical notes tying back to the thread: PLINQ has per‑item overhead and AsOrdered() adds cost — it shines only when each item is expensive to compute. For lookup-heavy logic use HashSet<int> (as hinted) rather than List<int>. For very large ranges consider a segmented sieve or a specialized library instead of per-number trial division.

Daniel_73 0 Newbie Poster

To improve speed, use a dictionary or hash table instead of List<int>.

ddanbe 2,724 Professional Procrastinator Featured Poster

It was not my intention to speed things up as I wanted to test the parallel feature. Thanks anyway.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.