Post

# LINQ and Prime Numbers

This program takes advantage of the power of LINQ to generate all prime numbers from 1 to 1,000,000.   It uses a technique that continues to filter out factorable numbers from the set of all integers up to 1,000,000 until only the primes are left.

The heart of the code is just 4 lines of C# using LINQ.  We simply cycle through all the numbers from 1-1,000,000 and check to see if the number is divisible by the next possible factor. Or if the number has already been checked for all possible factors we keep it in the set.  We only need to check divisors up until the square root of the last number in the set to cover all possible factors:

for (int div = 2; div < Math.Sqrt(numbersToSearchTo); div++)
{

var numbers = from num in allNumbers where num%div != 0 || div >=
num
select num;

allNumbers = numbers.ToList<int>();
}

Here is the Full Code:
------------------

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

namespace LinqTest

{

class Program

{

static void Main(string[] args)

{

List<int> allNumbers =new List<int>();

int numbersToSearchTo = 1000000;

// generate a list of numbers from 1 - 1,000,000

var allNumbersVar = System.Query.Sequence.Range(2, numbersToSearchTo - 1);

allNumbers = allNumbersVar.ToList<int>();

// cycle through all numbers and use LINQ to pull out the non-primes
// using the mod function in the where clause

for (int div = 2; div < Math.Sqrt(numbersToSearchTo); div++)
{

var numbers = from num in allNumbers where num%div != 0 || div >=
num
select num;

allNumbers = numbers.ToList<int>();
}

// show the results on the console

foreach (var num in allNumbers)

{

Console.Write("{0}, ", num);

}

Console.WriteLine();

Console.WriteLine();

Console.WriteLine("There are {0} Prime numbers in the set of 1-{1}.", allNumbers.Count, numbersToSearchTo);