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

ddanbe 0 Tallied Votes 365 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);
        }
    }
}
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.