快速获取第N个素数

算法原理：

判断一个数是否是素数，只要判断这个数是否可以被比这个数的平方根小的素数整除就可以了。因此下面用了一个List的变量来顺序存放每一个比这个数小的素数，（如果用的是VS2003的话，可以改用ArrayList类型的变量来存）。这个算法的效率还是比较高的，N=10000时，只需160毫秒；N=100000，需要1.5秒；N=1000000，需38秒。





view plaincopy to clipboardprint?
static long GetNPrime(int count)//返回第count个素数
{
List list = new List();//顺序存放素数
long startNumber = 1;
while (list.Count < count)
{
if (IsPrime(startNumber, list)) list.Add(startNumber);
startNumber++;
}
return --startNumber;
}

static bool IsPrime(long number, List list)//判断number是否为素数
{
if (number == 1) return false;
long max = (long)Math.Sqrt(number);
foreach (long n in list)
{
if (number % n == 0) return false;
if (n > max) break;
}
return true;
}
static long GetNPrime(int count)//返回第count个素数
{
List list = new List();//顺序存放素数
long startNumber = 1;
while (list.Count < count)
{
if (IsPrime(startNumber, list)) list.Add(startNumber);
startNumber++;
}
return --startNumber;
}

static bool IsPrime(long number, List list)//判断number是否为素数
{
if (number == 1) return false;
long max = (long)Math.Sqrt(number);
foreach (long n in list)
{
if (number % n == 0) return false;
if (n > max) break;
}
return true;
}