题
什么是最优雅的方式来执行这一功能:
ArrayList generatePrimes(int n)
这个函数产生第一个 n
素(编辑:哪里 n>1
),所以 generatePrimes(5)
将返回 ArrayList
与 {2, 3, 5, 7, 11}
.(我这样做在C#但我很高兴与Java实施或任何其他类似的语言对于这个问题(所以不Haskell)).
我不知道该怎么写这个的功能,但是当我做到了昨晚没有最终成为好,因为我是希望。这里是我想出了:
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;
}
我不太关心的速度,虽然我不想让它显然效率低下。我不介意哪种方法被用于(幼稚或筛或其他任何东西),但我希望它是相当短的和显而易见的,它是如何工作的。
编辑:感谢所有作了答复,虽然许多没有回答我的实际问题。重申,我想要一个干净漂亮的一块代码生成的一个列表中的总数。我已经知道如何做到这一群不同的方式,但我很容易编写代码,不是明确的,因为它可能是。在这个线程的几个好的选择已经提出:
- 一个更好的版本为什么我最初曾(彼得Smit,jmservera和Rekreativc)
- 一个非常干净的执行情况的筛埃拉托塞尼(starblue)
- 用爪哇的
BigInteger
s和nextProbablePrime
非常简单的代码,尽管我不能想象它是特别有效的(外交部) - 使用皇宫到延迟产生的清单素(Maghis)
- 把大量的素数的一个文本文件和阅读它们在必要时(达林)
编辑2:我 实现C# 一对夫妇的方法在这里给出,另一种方法,此处不再赘述。他们都发现第一 n 素有效地(和我有一个 体面的方法 找到的限制提供的筛).
解决方案 2
非常感谢所有谁给了有益的答案。这里是我的实现方式中的几种不同的方法找到第一 n 质数。前两个方法都是几乎什么发布这里。(海报名称旁边的标题。) 我计划做的筛阿特金的某个时候,虽然我怀疑它会不会是相当简单的方法在这里。如果任何人都可以看到任何方式改进这些方法我很想知道:-)
标准方法 (彼得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;
}
这已经优化只有通过测试对于可分割的平方根的数目正在进行测试;并且只有通过测试奇数。这可以进一步优化通过测试只有数字的形式 6k+[1, 5]
, 或 30k+[1, 7, 11, 13, 17, 19, 23, 29]
或 所以上.
筛埃拉托塞尼 (starblue)
这找到的所有要素 k.做一个列表中的第一个 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;
}
筛孙达拉姆
我才发现 这个筛 最近,但可以实现相当简单。我的执行情况不尽快筛埃拉托塞尼,但它是明显快于幼稚的方法。
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;
}
其他提示
使用的估计
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;
}
Ressurecting一个老问题,但是我偶然发现了它同时与皇宫.
这个代码的要求。NET4.0or。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();
}
你是在良好的道路。
一些评论意见
素数。添加(3);使这种功能不适用于数量=1
你没有测试,该司与primenumbers更大的平方根的数量进行测试。
建议的代码:
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;
}
你应该看看 可能素.特别是看一看 随机的算法 和 Miller–Rabin素性测试.
为完整起见,你只能使用 java。数学。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);
}
}
没有高效的,但也许最阅读:
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;
}
事实上只是一个变化的一些员额在这里有更好的格式。
我知道你要求非Haskell的解决方案,但我,包括在这里,因为它涉及的问题,也Haskell是美丽的这种类型的事情。
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 n p = n `mod` p == 0
使用一个总理 数发生器 创建primes.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 可能是明显较大。
我可以提供以下C#解决方案。它不快,但是很清楚它做什么。
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;
}
我离开了任何检查,如果限制是负数或小于两个(目前的方法将总是至少返回的两个因素).但是,这一切都容易解决。
更新
与以下两个扩展方法
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;
}
它的效率较低(因为广场根本作为重新评估往往),但它是更清洁的代码。它可以重写代码,懒洋洋地列举素数,但这将杂乱的代码。
这是一个实现的 筛埃拉托塞尼 在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
}
2009年的版权通过圣Wittum13189柏林德国在CC-通过-SA许可证 https://creativecommons.org/licenses/by-sa/3.0/
简单但最优雅的方式来计算所有素将是这个, 但是,这种方式是缓慢和记忆的成本远高于较高的数字 因为使用的教师(!) 功能...但是它展示了一种变化 威尔逊Theoreme在应用程序生成的所有素数的算法 实现蟒蛇
#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
if f%p%2:
print p
p+=1
f*=(p-2)
使用相同的算法你就可以做到这一点短:
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);
}
我写了一个简单的埃拉托塞尼实现c#中使用的一些皇宫.
不幸的是皇宫没有提供一个无限的序列整数所以你必须使用int。MaxValue:(
我得缓存在anonimous类型的候选sqrt避免以计算出它对每个缓存总理(看起来有点丑).
我用一个的列表之前素,直到sqrt的候选人
cache.TakeWhile(c => c <= candidate.Sqrt)
和检查每一个Int开始从2对它
.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;
}
}
另一个优化的是避免检查,甚至数字和返回仅有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;
}
}
为了使它更优雅,你应该重构你IsPrime测试纳入一个单独的方法,并处理循环,并增加外。
我没有在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;
}
});
}
});
这里是蟒蛇码的例子,打印出的总数低于两个百万:
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
这是最优雅我可以认为短的通知。
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;
}
希望这有助于给你一个想法。我敢肯定这是可以优化,但是它应该给你一个想法,你如何版本可以作出更多优雅。
编辑: 如在评论这个算法的确返回了错误的价值观为numberToGenerate < 2.我只想指出,我并不想以后他一个伟大的方法来生成素数(看看亨利的回答)我是mearly指出如何他方法可以更优雅。
使用基于流的方案编制 功能Java, 我想出了以下。的类型 Natural
基本上是一个 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()));
现在你有一个价值,你可以随身携带的,这是一个无限的流素数。你可以做的事情是这样的:
// 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));
一个解释的筛:
- 假设的第一个号码的参数流是总理,并把它放在前面的回流。其余的返回流是一个计算会产生的,只有当提出的要求。
- 如果有人要求对其余流,呼筛上的其余论点流,筛选了数量可分割的,由第一数目(其余部分分为零)。
你需要有以下进口:
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;
我个人认为这是一个相当简短和简洁(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;
}
试试这个皇宫查询时,它会产生总理的数字作为你的期望
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();
// 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("");
最简单的方法是试验和错误:你尝试,如果之间的任何数字2和n-1把你的候选总理。
第一个快捷方式是当然了)你只需要检查奇数,并b)只甲肝的检查为分隔达sqrt(n)。
在你的情况下,在生成的所有先前素数的过程作好了,你只需要检查是否任何素在你的名单,最多sqrt(n),分。
应该以最快的速度你可以得到你的钱:-)
编辑
Ok,你问吧。但我警告你:-),这是5分钟快速和肮脏的德尔菲码:
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;
要找出第100总理的数字,下列代码可以考虑的。
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);
我得到这个通过一读的"筛阿特金"在Wikki加一些现有的以为我已经给予这个-我花了很多时间编码从头开始,并获得完全的零关于人们正在关键的我编译器一样,非常密编码的风格+我甚至还没有完成第一次尝试运行的代码...许多范例,我已经学会了用在这里,只是读和哭泣,那什么,你可以。
以绝对和完全确定真正测试这一切之前的任何使用的,肯定没有显示任何人-这是为了阅读和考虑的想法。我需要让素性工具的工作因此,这是我开始的每一次我都得到什么工作。
得到一个清理汇编,然后开始采取什么是有缺陷的-我已经几乎108万键击的可用的代码这样做,这种方式,...使用什么,你可以。
我将在我的版本明天。
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
试试这个代码。
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质数