最优雅的方式来产生素数

什么是最优雅的方式来实现这个function：

ArrayList generatePrimes(int n) 

这个函数生成前n素数（编辑：其中n>1 ），所以generatePrimes(5)将返回一个ArrayList {2, 3, 5, 7, 11} ArrayList {2, 3, 5, 7, 11} 。 （我在C＃中这样做，但我很满意Java的实现 – 或者其他类似的语言（所以不是Haskell））。

我知道如何写这个function，但是当我昨晚做了这个function的时候，并没有像我希望的那样好。 这是我想出来的：

 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; } 

我不太在意速度，虽然我不希望它显然是低效的。 我不介意使用哪种方法（天真或筛选或其他），但我希望它是相当短暂和明显的如何工作。

编辑 ：感谢所有谁回应，虽然很多没有回答我的实际问题。 重申一下，我想要一个很好的代码，生成一个素数列表。 我已经知道如何做很多不同的方式，但是我倾向于编写不太清晰的代码。 在这个线程中已经提出了一些很好的select：

• 我最初的一个更好的版本（Peter Smit，jmservera和Rekreativc）
• 一个非常干净的Eratosthenes筛（starblue）
• 使用Java的BigInteger和nextProbablePrime来获得非常简单的代码，尽pipe我无法想象它是非常有效的（dfa）
• 使用LINQ来懒散地生成素数列表（Maghis）
• 在文本文件中join许多素数，并在必要时读取（darin）

编辑2 ：我已经在C＃中实现了一些在这里给出的方法，另一种方法没有在这里提到。 他们都有效地find了前n个素数（我有一个体面的方法来find限制提供给筛子）。

Answer 1

使用估计

 pi(n) = n / log(n) 

对于达到n的素数达到极限，然后使用筛子。 这个估计值低估了n的素数，所以筛比稍微大一些，这没问题。

这是我的标准Java筛，在普通的笔记本电脑上计算了第一百万个素数：

 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 2

非常感谢所有谁给了有用的答案。 这是我在C＃中find前n个素数的几种不同方法的实现。 前两种方法几乎是在这里发布的。 （海报的名字就在标题旁边）。我计划在某个时候对Atkin进行筛选，尽pipe我怀疑它不会像目前的方法那么简单。 如果有人能看到改进这些方法的任何方法，我很想知道:-)

标准方法 （ Peter Smit ， jmservera ， Rekreativc ）

第一个素数是2.添加到素数列表。 下一个数字是下一个数字，不能被列表中的任何数字整除。

 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; } 

这已经通过只testing可检测的数字的平方根进行了优化， 并且只testing奇数。 这可以通过仅testing6k+[1, 5] ，或30k+[1, 7, 11, 13, 17, 19, 23, 29] 6k+[1, 5]等等的数字来进一步优化。

Eratosthenes的筛子 （ starblue ）

这find了所有的素数 。 要列出前n个素数，我们首先需要近似第n个素数的值。 如下所述 ，下面的方法是这样做的。

 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; } 

Sundaram筛子

我最近才发现这个筛子 ，但它可以很简单地实现。 我的实现并不像Eratosthenes的筛选那样快，但它比天真的方法快得多。

 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 3

回顾一个老问题，但是我在玩LINQ的时候偶然发现了这个问题。

此代码需要使用并行扩展的.NET4.0或.NET3.5

 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

你正走在好路上。

一些意见

• primes.Add（3）; 使这个函数不适用于数字= 1

• 你不需要testing这个分区的主要数字大于被测数字的平方根。

build议的代码：

 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

你应该看看可能的素数 。 特别要看看随机algorithm和Miller-Rabin素数testing 。

为了完整起见，您可以使用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

我知道你问了非Haskell的解决scheme，但我在这里包括这个问题，因为它涉及到这个问题，而且Haskell对于这种types的事情是美丽的。

 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 7

使用素数生成器来创buildprimes.txt，然后：

 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); } } } 

在这种情况下，我在方法签名中使用Int16，所以我的primes.txt文件包含从0到32767的数字。如果要将其扩展到Int32或Int64，则您的primes.txt可能会更大。

Answer 8

我可以提供以下C＃解决scheme。 这并不是很快，但是它的作用非常明确。

 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; } 

我忽略了任何检查 – 如果限制是负数或小于2（目前该方法至less会返回两个素数）。 但是这很容易解决。

UPDATE

通过以下两种扩展方法

 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; } } 

你可以重写它如下。

 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; } 

效率较低（因为经常重新评估平方根），但它更简洁。 可以重写代码来懒散地枚举素数，但是这会使代码杂乱不堪。

Answer 9

这是C＃ 中Eratosthenes的一个实现：

  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

绝不是有效的，但也许是最可读的：

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

有：

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

其实只是一些更好的格式的职位的变化。

Answer 11

使用相同的algorithm，可以缩短一点：

 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

版权2009由St.Wittum 13189 Berlin GERMANY根据CC-BY-SA许可证https://creativecommons.org/licenses/by-sa/3.0/

计算所有PRIMES的简单但是最优雅的方法就是这样，但是这种方法很慢，而且因为使用faculty（！）函数，所以对于更高的数字，内存成本要高得多……但是它展示了Wilson Theoreme在应用程序中的变化通过在Python中实现的algorithm生成所有素数

 #!/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

我用c＃写了一个简单的Eratosthenes实现，使用了一些LINQ。

不幸的是LINQ不提供无限的整数序列，所以你必须使用int.MaxValue 🙁

我不得不caching在候选的sqrttypes，以避免计算每个caching的素数（看起来有点难看）。

我使用以前的素数列表直到候选人的sqrt

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

从2开始检查每个Int

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

这里是代码：

 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; } } 

另一个优化是避免检查偶数，并在创build列表之前返回2。 这样，如果调用方法只是要求1个素数，它将避免所有的混乱：

 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

为了使它更加优雅，你应该把你的IsPrimetesting重构成一个单独的方法，并处理循环和增量。

Answer 15

我在Java中使用我编写的函数库做了它，但由于我的库使用与枚举相同的概念，我相信代码是可适应的：

 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 16

这里是一个python代码示例，打印出所有素数低于200万的总和：

 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 17

这是我能在短时间内想到的最优雅的。

 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; } 

希望这有助于给你一个想法。 我相信这可以优化，但它应该给你一个想法，你的版本可以变得更加优雅。

编辑：正如在注释中指出的，这个algorithm确实返回了numberToGenerate <2的错误值。我只想指出，我并不是想要发布一个很好的方法来生成素数（请看亨利的答案），我很清楚地指出他的方法可以变得更加优雅。

Answer 18

在Functional Java中使用基于stream的编程，我想出了以下内容。 Naturaltypes本质上是一个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())); 

现在你有一个价值，你可以随身携带，这是一个无限的素数stream。 你可以做这样的事情：

 // 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)); 

筛子的解释：

1. 假设参数stream中的第一个数字是素数，并将其放在返回stream的前面。 返回stream的其余部分是只有在被要求时才会产生的计算。
2. 如果有人要求stream的其余部分，则在参数stream的其余部分调用sieve，过滤掉可被第一个数字整除的数字（除法的其余部分为零）。

您需要有以下导入：

 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

我个人认为这是一个非常简洁的（Java）实现：

 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

试试这个LINQ查询，它会按照您的预期生成素数

  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

最简单的方法是反复试验：如果2和n-1之间的任意数字将候选素数n分开，则尝试。
第一个捷径当然是a）你只需要检查奇数，b）你只需要检查sqrt（n）的分频器。

在你的情况下，你也可以在这个过程中生成所有以前的素数，只需要检查列表中的任何素数（sqrt（n））是否除以n。
应该是最快的，你可以得到你的钱:-)

编辑
好，代码，你问了。 但是我警告你:-)，这是一个5分钟快捷的Delphi代码：

 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

要找出前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 24

我在Wikki上读了一下“Atkin Sieve”，加上我曾经给过的一些想法 – 我花了很多时间从头开始编写代码，并且完全清除了那些对编译器非常敏感的代码风格+我甚至还没有做第一次尝试运行代码…我已经学会使用的许多范例在这里，只是阅读和哭泣，得到你可以。

在使用之前，绝对要确保完全testing所有这些，当然不要把它展示给任何人 – 这是为了阅读和思考的想法。 我需要得到有价值的工具，所以这是我每次开始工作的地方。

得到一个干净的编译，然后开始拿走有缺陷的东西 – 我有近1.08亿的可用代码按这样做，…使用你可以。

我明天将在我的版本上工作。

 package demo; // This code is a discussion of an opinion in a technical forum. // It's 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 25

试试这个代码。

 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(); } 

Here is the aspx code.

 <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> 

Results: 10000 Prime Numbers in less than one second

100000 Prime Numbers in 63 seconds

Screenshot of first 100 Prime Numbers