The most elegant way to generate prime numbers

Question

What is the most elegant way to implement this feature:

ArrayList generatePrimes(int n) 

This function generates the first n prime numbers (edit: where n>1 ), so generatePrimes(5) will return an ArrayList using {2, 3, 5, 7, 11} . (I do this in C #, but I'm happy with the Java implementation or any other similar language (so not Haskell)).

I know how to write this function, but when I did it last night, it did not end as good as I had hoped. Here is what I came up with:

 ArrayList generatePrimes(int toGenerate) { ArrayList primes = new ArrayList(); primes.Add(2); primes.Add(3); while (primes.Count < toGenerate) { int nextPrime = (int)(primes[primes.Count - 1]) + 2; while (true) { bool isPrime = true; foreach (int n in primes) { if (nextPrime % n == 0) { isPrime = false; break; } } if (isPrime) { break; } else { nextPrime += 2; } } primes.Add(nextPrime); } return primes; } 

I am not too concerned about speed, although I do not want it to be clearly ineffective. I don't mind which method is used (naive or sieve or something else), but I want it to be short enough and obvious how this works.

Change Thanks to everyone who answered, although many did not answer my question. I repeat, I need a nice clean piece of code that generated a list of primes. I already know how to do it in different ways, but I tend to write code that is not as clear as it could be. Several good options have been suggested in this thread:

• A nicer version of what I originally had (Peter Smit, jmservera and Rekreativc)
• Very clean implementation of Eratosthenes sieve (starblue)
• Use Java BigInteger and nextProbablePrime for very simple code, although I cannot imagine that it is particularly efficient (dfa)
• Use LINQ to lazily create a list of primes (Maghis)
• Put a lot of simple ones in a text file and read them when necessary (darin)

Edit 2 : I implemented in C # a couple of the methods given here and another method not mentioned here. They all find the first n prime numbers efficiently (and I have a decent method of finding the limit for providing sieves).

Answer 1

Many thanks to everyone who gave helpful answers. Here are my implementations of several different search methods for the first n primes in C #. The first two methods are what was published here. (Poster names are next to the name.) I plan to make an Atkin sieve someday, although I suspect it will not be as simple as the methods here at present. If anyone can see any way to improve any of these methods, I would love to know :-)

Standard Method ( Peter Smith , jmservera , Rekreativc )

The first prime number is 2. Add this to the list of primes. The next number is the next number that is not evenly divided by any number in this list.

 public static List<int> GeneratePrimesNaive(int n) { List<int> primes = new List<int>(); primes.Add(2); int nextPrime = 3; while (primes.Count < n) { int sqrt = (int)Math.Sqrt(nextPrime); bool isPrime = true; for (int i = 0; (int)primes[i] <= sqrt; i++) { if (nextPrime % primes[i] == 0) { isPrime = false; break; } } if (isPrime) { primes.Add(nextPrime); } nextPrime += 2; } return primes; } 

This was optimized only when checking for divisibility to the square root of the number being tested; and only testing odd numbers. This can be further optimized by testing only numbers of the form 6k+[1, 5] or 30k+[1, 7, 11, 13, 17, 19, 23, 29] or so on .

Eratosthenes sieve ( starblue )

This finds all primes up to k . To make a list of the first n primes, we first need to get closer to the value of the nth number. The following method, as described here , does this.

 public static int ApproximateNthPrime(int nn) { double n = (double)nn; double p; if (nn >= 7022) { p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385); } else if (nn >= 6) { p = n * Math.Log(n) + n * Math.Log(Math.Log(n)); } else if (nn > 0) { p = new int[] { 2, 3, 5, 7, 11 }[nn - 1]; } else { p = 0; } return (int)p; } // Find all primes up to and including the limit public static BitArray SieveOfEratosthenes(int limit) { BitArray bits = new BitArray(limit + 1, true); bits[0] = false; bits[1] = false; for (int i = 0; i * i <= limit; i++) { if (bits[i]) { for (int j = i * i; j <= limit; j += i) { bits[j] = false; } } } return bits; } public static List<int> GeneratePrimesSieveOfEratosthenes(int n) { int limit = ApproximateNthPrime(n); BitArray bits = SieveOfEratosthenes(limit); List<int> primes = new List<int>(); for (int i = 0, found = 0; i < limit && found < n; i++) { if (bits[i]) { primes.Add(i); found++; } } return primes; } 

Sieve of Sundarama

I recently discovered this sieve , but it can be implemented quite simply. My implementation is not as fast as the Eratosthenes lattice, but it is much faster than the naive method.

 public static BitArray SieveOfSundaram(int limit) { limit /= 2; BitArray bits = new BitArray(limit + 1, true); for (int i = 1; 3 * i + 1 < limit; i++) { for (int j = 1; i + j + 2 * i * j <= limit; j++) { bits[i + j + 2 * i * j] = false; } } return bits; } public static List<int> GeneratePrimesSieveOfSundaram(int n) { int limit = ApproximateNthPrime(n); BitArray bits = SieveOfSundaram(limit); List<int> primes = new List<int>(); primes.Add(2); for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++) { if (bits[i]) { primes.Add(2 * i + 1); found++; } } return primes; } 

Answer 2

Use rating

 pi(n) = n / log(n) 

for the number of primes to n, to find the limit, and then use a sieve. Evaluation underestimates the number of primes to n, so the sieve will be slightly larger than necessary, which is good.

This is my standard Java sieve, calculates the first millions of primes in about a second on a regular laptop:

 public static BitSet computePrimes(int limit) { final BitSet primes = new BitSet(); primes.set(0, false); primes.set(1, false); primes.set(2, limit, true); for (int i = 0; i * i < limit; i++) { if (primes.get(i)) { for (int j = i * i; j < limit; j += i) { primes.clear(j); } } } return primes; } 

Answer 3

Reexamining the old question, but I came across it while playing with LINQ.

This code requires .NET4.0 or .NET3.5 with parallel extensions

 public List<int> GeneratePrimes(int n) { var r = from i in Enumerable.Range(2, n - 1).AsParallel() where Enumerable.Range(2, (int)Math.Sqrt(i)).All(j => i % j != 0) select i; return r.ToList(); } 

Answer 4

You are on a good path.

Some comments

• primes.Add (3); that this function does not work for number = 1

• You do not need to check the division with examples that are larger than the square of the number of the number checked.

Suggested code:

 ArrayList generatePrimes(int toGenerate) { ArrayList primes = new ArrayList(); if(toGenerate > 0) primes.Add(2); int curTest = 3; while (primes.Count < toGenerate) { int sqrt = (int) Math.sqrt(curTest); bool isPrime = true; for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i) { if (curTest % primes.get(i) == 0) { isPrime = false; break; } } if(isPrime) primes.Add(curTest); curTest +=2 } return primes; } 

Answer 5

you should take a look at the probable primes . In particular, take a look at Randomized Algorithms and the Miller-Rabin Primitive Test .

For completeness, you can simply use java.math.BigInteger :

 public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> { private BigInteger p = BigInteger.ONE; @Override public boolean hasNext() { return true; } @Override public BigInteger next() { p = p.nextProbablePrime(); return p; } @Override public void remove() { throw new UnsupportedOperationException("Not supported."); } @Override public Iterator<BigInteger> iterator() { return this; } } @Test public void printPrimes() { for (BigInteger p : new PrimeGenerator()) { System.out.println(p); } } 

Answer 6

Use a simple number generator to create primes.txt, and then:

 class Program { static void Main(string[] args) { using (StreamReader reader = new StreamReader("primes.txt")) { foreach (var prime in GetPrimes(10, reader)) { Console.WriteLine(prime); } } } public static IEnumerable<short> GetPrimes(short upTo, StreamReader reader) { int count = 0; string line = string.Empty; while ((line = reader.ReadLine()) != null && count++ < upTo) { yield return short.Parse(line); } } } 

In this case, I use Int16 in the method signature, so the primes.txt file contains numbers from 0 to 32767. If you want to extend this to Int32 or Int64, your primes.txt can be significantly larger.

Answer 7

I know that you asked for solutions other than Haskell, but I include this here as it concerns the question, and also Haskell is fine for this type.

 module Prime where primes :: [Integer] primes = 2:3:primes' where -- Every prime number other than 2 and 3 must be of the form 6k + 1 or -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as -- prime (6*0+5 == 5) to start the recursion. 1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]] primes' = p : filter isPrime candidates isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes' divides np = n `mod` p == 0 

Answer 8

I can suggest the following C # solution. This is by no means fast, but it is very clear what he is doing.

 public static List<Int32> GetPrimes(Int32 limit) { List<Int32> primes = new List<Int32>() { 2 }; for (int n = 3; n <= limit; n += 2) { Int32 sqrt = (Int32)Math.Sqrt(n); if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0)) { primes.Add(n); } } return primes; } 

I did not perform any checks - if the limit is negative or less than two (at the moment, the method will always return at least two as a simple one). But all this is easy to fix.

UPDATE

Use the following two extension methods

 public static void Do<T>(this IEnumerable<T> collection, Action<T> action) { foreach (T item in collection) { action(item); } } public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step) { for (int i = start; i < end; i += step) } yield return i; } } 

You can rewrite it as follows.

 public static List<Int32> GetPrimes(Int32 limit) { List<Int32> primes = new List<Int32>() { 2 }; Range(3, limit, 2) .Where(n => primes .TakeWhile(p => p <= Math.Sqrt(n)) .All(p => n % p != 0)) .Do(n => primes.Add(n)); return primes; } 

This is less efficient (because the square root is reevaluated quite often), but it is even cleaner code. You can rewrite the code to lazily enumerate primes, but this is a bit cluttered with code.

Answer 9

Here's the implementation of Sieve Eratosthenes in C #:

  IEnumerable<int> GeneratePrimes(int n) { var values = new Numbers[n]; values[0] = Numbers.Prime; values[1] = Numbers.Prime; for (int outer = 2; outer != -1; outer = FirstUnset(values, outer)) { values[outer] = Numbers.Prime; for (int inner = outer * 2; inner < values.Length; inner += outer) values[inner] = Numbers.Composite; } for (int i = 2; i < values.Length; i++) { if (values[i] == Numbers.Prime) yield return i; } } int FirstUnset(Numbers[] values, int last) { for (int i = last; i < values.Length; i++) if (values[i] == Numbers.Unset) return i; return -1; } enum Numbers { Unset, Prime, Composite } 

Answer 10

Not at all effective, but perhaps the most widely read:

 public static IEnumerable<int> GeneratePrimes() { return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate))) .All(divisor => candidate % divisor != 0)); } 

from:

 public static IEnumerable<int> Range(int from, int to = int.MaxValue) { for (int i = from; i <= to; i++) yield return i; } 

This is actually just a variation of some of the posts here with better formatting.

Answer 11

Using the same algorithm, you can do this a little shorter:

 List<int> primes=new List<int>(new int[]{2,3}); for (int n = 5; primes.Count< numberToGenerate; n+=2) { bool isPrime = true; foreach (int prime in primes) { if (n % prime == 0) { isPrime = false; break; } } if (isPrime) primes.Add(n); } 

Answer 12

Copyright 2009 by St. Wittum 13189 Berlin GERMANY licensed under CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/

A simple but most elegant way to calculate ALL PREMIERES would be this, but this path is slow and the memory costs are much higher for higher numbers because using the faculty function (!) ... but it demonstrates a variation of Wilson's theorem in the application for generating all simple numbers by algorithm implemented in Python

 #!/usr/bin/python f=1 # 0! p=2 # 1st prime while True: if f%p%2: print p p+=1 f*=(p-2) 

Answer 13

I wrote a simple implementation of Eratosthenes in C # using some LINQ.

Unfortunately, LINQ does not provide an infinite int sequence, so you need to use int.MaxValue: (

I had to cache the sqrt candidate in an anonymous type to avoid calculating it for every cached prime (it looks a bit ugly).

I use a list of previous prime numbers up to sqrt candidate

 cache.TakeWhile(c => c <= candidate.Sqrt) 

and check every int starting at 2 against it

 .Any(cachedPrime => candidate.Current % cachedPrime == 0) 

Here is the code:

 static IEnumerable<int> Primes(int count) { return Primes().Take(count); } static IEnumerable<int> Primes() { List<int> cache = new List<int>(); var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new { Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance Current = candidate }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt) .Any(cachedPrime => candidate.Current % cachedPrime == 0)) .Select(p => p.Current); foreach (var prime in primes) { cache.Add(prime); yield return prime; } } 

Another optimization is to avoid checking even numbers and return only 2 before creating the list. Thus, if the calling method simply requests 1 prime, it will avoid all the mess:

 static IEnumerable<int> Primes() { yield return 2; List<int> cache = new List<int>() { 2 }; var primes = Enumerable.Range(3, int.MaxValue - 3) .Where(candidate => candidate % 2 != 0) .Select(candidate => new { Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance Current = candidate }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt) .Any(cachedPrime => candidate.Current % cachedPrime == 0)) .Select(p => p.Current); foreach (var prime in primes) { cache.Add(prime); yield return prime; } } 

Answer 14

This is the most elegant that I can think of in a short time.

 ArrayList generatePrimes(int numberToGenerate) { ArrayList rez = new ArrayList(); rez.Add(2); rez.Add(3); for(int i = 5; rez.Count <= numberToGenerate; i+=2) { bool prime = true; for (int j = 2; j < Math.Sqrt(i); j++) { if (i % j == 0) { prime = false; break; } } if (prime) rez.Add(i); } return rez; } 

Hope this helps you give you an idea. I'm sure this can be optimized, but it should give you an idea of ​​how your version can be more elegant.

EDIT: As noted in the comments, this algorithm does return incorrect values ​​for numberToGenerate <2. I just want to point out that I did not try to publish a great method for generating prime numbers (look at Henri's answer for this), I viciously pointed out how it the method can be made more elegant.

Answer 15

To make it more elegant, you must reorganize your IsPrime test into a separate method and process the loop and extend it outside.

Answer 16

I did this in Java using the functional library I wrote, but since my library uses the same concepts as enumerations, I am sure that the code can be adapted:

 Iterable<Integer> numbers = new Range(1, 100); Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>() { public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception { // We don't test for 1 which is implicit if ( number <= 1 ) { return numbers; } // Only keep in numbers those that do not divide by number return numbers.reject(new Functions.Predicate1<Integer>() { public Boolean call(Integer n) throws Exception { return n > number && n % number == 0; } }); } }); 

Answer 17

Here is an example python code that prints the sum of all primes below two million:

 from math import * limit = 2000000 sievebound = (limit - 1) / 2 # sieve only odd numbers to save memory # the ith element corresponds to the odd number 2*i+1 sieve = [False for n in xrange(1, sievebound + 1)] crosslimit = (int(ceil(sqrt(limit))) - 1) / 2 for i in xrange(1, crosslimit): if not sieve[i]: # if p == 2*i + 1, then # p**2 == 4*(i**2) + 4*i + 1 # == 2*i * (i + 1) for j in xrange(2*i * (i + 1), sievebound, 2*i + 1): sieve[j] = True sum = 2 for i in xrange(1, sievebound): if not sieve[i]: sum = sum + (2*i+1) print sum 

Answer 18

Using streaming programming in Functional Java , I came up with the following. The type of Natural is essentially BigInteger > = 0.

 public static Stream<Natural> sieve(final Stream<Natural> xs) { return cons(xs.head(), new P1<Stream<Natural>>() { public Stream<Natural> _1() { return sieve(xs.tail()._1() .filter($(naturalOrd.equal().eq(ZERO)) .o(mod.f(xs.head())))); }}); } public static final Stream<Natural> primes = sieve(forever(naturalEnumerator, natural(2).some())); 

Now you have a value that you can carry with you, which is an endless stream of primes. You can do things like this:

 // Take the first n primes Stream<Natural> nprimes = primes.take(n); // Get the millionth prime Natural mprime = primes.index(1000000); // Get all primes less than n Stream<Natural> pltn = primes.takeWhile(naturalOrd.lessThan(n)); 

Sieve explanation:

• Suppose that the first number in the argument stream is prime and places it at the beginning of the return stream. The rest of the return flow is a calculation that will only be performed on request.
• If someone asks for the rest of the stream, call a sieve on the rest of the argument stream, filtering out the numbers divisible by the first number (the remainder of the division is zero).

You must have the following imports:

 import fj.P1; import static fj.FW.$; import static fj.data.Enumerator.naturalEnumerator; import fj.data.Natural; import static fj.data.Natural.*; import fj.data.Stream; import static fj.data.Stream.*; import static fj.pre.Ord.naturalOrd; 

Answer 19

I personally think this is a rather short and clean (Java) implementation:

 static ArrayList<Integer> getPrimes(int numPrimes) { ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes); int n = 2; while (primes.size() < numPrimes) { while (!isPrime(n)) { n++; } primes.add(n); n++; } return primes; } static boolean isPrime(int n) { if (n < 2) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } int d = 3; while (d * d <= n) { if (n % d == 0) { return false; } d += 2; } return true; } 

Answer 20

Try this LINQ query, it generates prime numbers as you expected

  var NoOfPrimes= 5; var GeneratedPrime = Enumerable.Range(1, int.MaxValue) .Where(x => { return (x==1)? false: !Enumerable.Range(1, (int)Math.Sqrt(x)) .Any(z => (x % z == 0 && x != z && z != 1)); }).Select(no => no).TakeWhile((val, idx) => idx <= NoOfPrimes-1).ToList(); 

Answer 21

 // Create a test range IEnumerable<int> range = Enumerable.Range(3, 50 - 3); // Sequential prime number generator var primes_ = from n in range let w = (int)Math.Sqrt(n) where Enumerable.Range(2, w).All((i) => n % i > 0) select n; // Note sequence of output: // 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, foreach (var p in primes_) Trace.Write(p + ", "); Trace.WriteLine(""); 

Answer 22

The easiest method is the trial version and the error: you try if any number between 2 and n-1 divides your candidate by n. The first shortcuts, of course, a) you only need to check odd numbers, and b) you can only check divisors before sqrt (n).

In your case, when you also generate all the previous primes in this process, you only need to check if any of the primes in your list are splitting up to sqrt (n) n.
It should be the fastest thing you can get for your money :-)

change
Ok code, you asked for it. But I warn you :-), this is the 5 minute fast and dirty Delphi code:

 procedure TForm1.Button1Click(Sender: TObject); const N = 100; var PrimeList: TList; I, J, SqrtP: Integer; Divides: Boolean; begin PrimeList := TList.Create; for I := 2 to N do begin SqrtP := Ceil(Sqrt(I)); J := 0; Divides := False; while (not Divides) and (J < PrimeList.Count) and (Integer(PrimeList[J]) <= SqrtP) do begin Divides := ( I mod Integer(PrimeList[J]) = 0 ); inc(J); end; if not Divides then PrimeList.Add(Pointer(I)); end; // display results for I := 0 to PrimeList.Count - 1 do ListBox1.Items.Add(IntToStr(Integer(PrimeList[I]))); PrimeList.Free; end; 

Answer 23

I got this in the first reading of Wikki's Atkin Sieve, as well as some previous thoughts I gave to it - I spend a lot of time coding from scratch and completely zero out when people criticize my compilers, very dense coding style + I don’t even made the first attempt to run the code ... many of the paradigm that I learned to use, here, just read and cry, get what you can.

Be absolutely sure that you will really experience all this before use, for sure do not show it to anyone - this is for reading and considering ideas. I need the primality tool to work, so I start every time I have to do something.

Get one clean compiler and then start selecting what is defective - I have almost 108 million clicks on the code used, doing it this way ... use what you can.

Tomorrow I will work on my version.

 package demo; // This code is a discussion of an opinion in a technical forum. // It use as a basis for further work is not prohibited. import java.util.Arrays; import java.util.HashSet; import java.util.ArrayList; import java.security.GeneralSecurityException; /** * May we start by ignores any numbers divisible by two, three, or five * and eliminate from algorithm 3, 5, 7, 11, 13, 17, 19 completely - as * these may be done by hand. Then, with some thought we can completely * prove to certainty that no number larger than square-root the number * can possibly be a candidate prime. */ public class PrimeGenerator<T> { // Integer HOW_MANY; HashSet<Integer>hashSet=new HashSet<Integer>(); static final java.lang.String LINE_SEPARATOR = new java.lang.String(java.lang.System.getProperty("line.separator"));// // PrimeGenerator(Integer howMany) throws GeneralSecurityException { if(howMany.intValue() < 20) { throw new GeneralSecurityException("I'm insecure."); } else { this.HOW_MANY=howMany; } } // Let us then take from the rich literature readily // available on primes and discount // time-wasters to the extent possible, utilizing the modulo operator to obtain some // faster operations. // // Numbers with modulo sixty remainder in these lists are known to be composite. // final HashSet<Integer> fillArray() throws GeneralSecurityException { // All numbers with modulo-sixty remainder in this list are not prime. int[]list1=new int[]{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30, 32,34,36,38,40,42,44,46,48,50,52,54,56,58}; // for(int nextInt:list1) { if(hashSet.add(new Integer(nextInt))) { continue; } else { throw new GeneralSecurityException("list1");// } } // All numbers with modulo-sixty remainder in this list are are // divisible by three and not prime. int[]list2=new int[]{3,9,15,21,27,33,39,45,51,57}; // for(int nextInt:list2) { if(hashSet.add(new Integer(nextInt))) { continue; } else { throw new GeneralSecurityException("list2");// } } // All numbers with modulo-sixty remainder in this list are // divisible by five and not prime. not prime. int[]list3=new int[]{5,25,35,55}; // for(int nextInt:list3) { if(hashSet.add(new Integer(nextInt))) { continue; } else { throw new GeneralSecurityException("list3");// } } // All numbers with modulo-sixty remainder in // this list have a modulo-four remainder of 1. // What that means, I have neither clue nor guess - I got all this from int[]list4=new int[]{1,13,17,29,37,41,49,53}; // for(int nextInt:list4) { if(hashSet.add(new Integer(nextInt))) { continue; } else { throw new GeneralSecurityException("list4");// } } Integer lowerBound=new Integer(19);// duh Double upperStartingPoint=new Double(Math.ceil(Math.sqrt(Integer.MAX_VALUE)));// int upperBound=upperStartingPoint.intValue();// HashSet<Integer> resultSet=new HashSet<Integer>(); // use a loop. do { // One of those one liners, whole program here: int aModulo=upperBound % 60; if(this.hashSet.contains(new Integer(aModulo))) { continue; } else { resultSet.add(new Integer(aModulo));// } } while(--upperBound > 20); // this as an operator here is useful later in your work. return resultSet; } // Test harness .... public static void main(java.lang.String[] args) { return; } } //eof 

Answer 24

100 , java.

 int num = 2; int i, count; int nPrimeCount = 0; int primeCount = 0; do { for (i = 2; i <num; i++) { int n = num % i; if (n == 0) { nPrimeCount++; // System.out.println(nPrimeCount + " " + "Non-Prime Number is: " + num); num++; break; } } if (i == num) { primeCount++; System.out.println(primeCount + " " + "Prime number is: " + num); num++; } }while (primeCount<100); 

Answer 25

Try this code.

 protected bool isPrimeNubmer(int n) { if (n % 2 == 0) return false; else { int j = 3; int k = (n + 1) / 2 ; while (j <= k) { if (n % j == 0) return false; j = j + 2; } return true; } } protected void btn_primeNumbers_Click(object sender, EventArgs e) { string time = ""; lbl_message.Text = string.Empty; int num; StringBuilder builder = new StringBuilder(); builder.Append("<table><tr>"); if (int.TryParse(tb_number.Text, out num)) { if (num < 0) lbl_message.Text = "Please enter a number greater than or equal to 0."; else { int count = 1; int number = 0; int cols = 11; var watch = Stopwatch.StartNew(); while (count <= num) { if (isPrimeNubmer(number)) { if (cols > 0) { builder.Append("<td>" + count + " - " + number + "</td>"); } else { builder.Append("</tr><tr><td>" + count + " - " + number + "</td>"); cols = 11; } count++; number++; cols--; } else number++; } builder.Append("</table>"); watch.Stop(); var elapsedms = watch.ElapsedMilliseconds; double seconds = elapsedms / 1000; time = seconds.ToString(); lbl_message.Text = builder.ToString(); lbl_time.Text = time; } } else lbl_message.Text = "Please enter a numberic number."; lbl_time.Text = time; tb_number.Text = ""; tb_number.Focus(); } 

aspx.

 <form id="form1" runat="server"> <div> <p>Please enter a number: <asp:TextBox ID="tb_number" runat="server"></asp:TextBox></p> <p><asp:Button ID="btn_primeNumbers" runat="server" Text="Show Prime Numbers" OnClick="btn_primeNumbers_Click" /> </p> <p><asp:Label ID="lbl_time" runat="server"></asp:Label></p> <p><asp:Label ID="lbl_message" runat="server"></asp:Label></p> </div> </form> 

: 10000

100000 63

100